perm filename V2K.IN[TEX,DEK] blob sn#285516 filedate 1977-05-29 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00015 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	folio 465 galley 1
C00014 00003	folio 468 galley 2
C00037 00004	folio 473 galley 3
C00055 00005	folio 476 galley 4
C00068 00006	folio 479 galley 5 WARNING: Tape mostly unreadable, NEXT TEN GALLEYS.
C00080 00007	folio 482 galley 6
C00095 00008	folio 488 galley 7
C00112 00009	folio 492 galley 8
C00131 00010	folio 496 galley 9
C00147 00011	folio 500 galley 10
C00163 00012	folio 505 galley 11
C00178 00013	folio 508 galley 12
C00196 00014	folio 512 galley 13
C00211 00015	folio 515 galley 14
C00224 ENDMK
C⊗;
folio 465 galley 1
    0  {U0}{H10L12M29}|πW58320#Computer Programming!ch. 
    2  4!f. 465!g. 1|'{A6}of ln|4|εX|βn |πis, to a very 
   11  good approximation,|'{A6}|ε|(|π1|d2ln|42|)|4|↔j|ur1|)0|)|4|(
   13  |πln|4|εx|d21|4α+↓|4x|)|4dx|4|∂α=↓|4α_↓|4|(|π1|d2ln|42|)|4|↔
   13  j|ur|¬1|)0|)|4|(|εue|gα_↓|gu|d21|4α+↓|4e|gα_↓|gu|)|4du|'
   14  {A4}|Lα=↓|4α_↓|4|(|π1|d2ln|42|)|4|↔k|uc|)|εk|1|1|¬¬C5|11|)|4
   14  (|→α_↓1)|gk|gα+↓|g1|4|↔j|ur|¬1|)0|)|4ue|gα_↓|gk|gu|4du>
   15  {A4}|Lα=↓|4α_↓|4|(|π1|d2ln|42|)|4(1|4α_↓|4|f1|d34|)|4α+↓|4|f
   15  1|d39|)|4α_↓|4|f1|d316|)|4α+↓|4|f1|d325|)|4α_↓|4αo↓|4αo↓|4αo
   15  ↓)>{A4}|Lα=↓|4α_↓|4|(|π1|d2ln|42|)|4(1|4α+↓|4|f1|d34|)|4α+↓|
   16  4|f1|d39|)|4α+↓|4αo↓|4αo↓|4αo↓|4α_↓|42(|f1|d34|)|4α+↓|4|f1|d
   16  316|)|4α+↓|4|f1|d336|)|4α+↓|4αo↓|4αo↓|4αo↓)|≥2>
   17  {A4}|Lα=↓|4α_↓|4|(|π1|d22|4ln|42|)|4(1|4α+↓|4|f1|d34|)|4α+↓|
   17  4|f1|d39|)|4α+↓|4αo↓|4αo↓|4αo↓)>{A4}|Lα=↓|4α_↓|ε|≤p|g2/12|4|
   18  πln|42.#>{A6}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
   19  }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
   19  }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
   19  }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
   19  }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
   19  }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
   19  }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
   19  }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
   19  }}}}}}|[π|πTherefore by (48) we expect to have 
   26  the approximate formula|'{A6}|ε|→α_↓t|≤p|g2/(12|4|πln|42)|4|
   29  ¬V|4|→α_↓ln|4|εN;|;{A6}|πthat is, |εt |πshould 
   34  be approximately proportional to (12|4ln|4|ε2/|≤p|g2)|4|πln|
   38  4|εN. |πThis constant (12|4ln|4|ε2/|≤p|g2)|4α=↓|40.842765913
   41  |4.|4.|4. |πagrees perfectly with the empirical 
   47  formula (47) obtained earlier, so we have good 
   55  reason to believe that the formula|'{A6}|ε|≤t|βn|4|¬V|4|(|π1
   61  2|4ln|42|d2|ε|≤p|g2|)|4|πln|4|εn|4α+↓|41.47|J!(51)|;
   62  {A6}|πindicates the true asymptotic behavior 
   67  of |ε|≤t|βn |πas |εn|4|¬M|4|¬X.|'|π!|9|4|1|1|1If 
   72  we assume that (51) is valid, we obtain the formula|'
   82  {A6|εT|βnN4|¬V|4←(*4π3264⊂n|426d2|ε*3*2*2|g2|)←↔a|πln|4|εn|4α_↓|
   82  4|↔k|uc|)dF1|¬D|1,N)←4←*/*3≤<|\(-)≡≠F↔?S4α~↓*441.67,]J!(52)*4;{A
   82  6}|πwqeje |*/|≤8|\|ε(-)?|πiss|ε#on Mangoldt's 
   85  function |πde_ned by the rules|'{A6}|ε|*/*/≤8|\(↔)←4α=↓|4|↔A|(
   90  |πln|4|εp,$!|πifs|εn|4α≡↓**4∀|gr |π↔brn|εp *4π#rime,$!|εr|4|¬R
   92  |41;|d5←πotherwise.|)|JD(53)|;{A2}|π'FbrcsxjxpleS'↓J*/}|ε⊗T|β
   93  1←β0←β0←44∪4¬}C44(*4[3364⊂cN466f↑6≥\*2*2Ig26)*4↔a|π⊂nN4100|4α_↓|
   93  4|(ln|42|d22|)|4α_↓|4|(⊂n|42|d26←)|4α_↓←4|(lnN45←d25←)|4α_↓|
   93  4|(ln|45|d225|)|↔s|4α+↓|41.47!|;{A4}|PP}}V4(.*4*/7*2(**.6π554≠↓|
   94  40.347|4α_↓|40.173←4α_↓|40.322|4α_↓|40.064)|4α+↓*441.47>
   95  {A4e|LI¬}C44.59;%↓J**}|πthesexjcg v¬wqusmxf|\*5HI14I1→I1→|[/us
   96  4777#[,'Offcvkjse weshavesnoo yez |ε∀rovddf|[≠kxzhicvvu∧bkq 
  100  |≥*5|icn|[≠kff|ε&|≤~|βnn|π∪n gendjal; so far we 
  105  have onlysbeen consideringcplausiblesrdaubmfswyyshhssa∧bvjsf
  107  xrvkqausok¬vhhhomhmg∧).FXggukkwewqsit issno∧upvxsu∧∧estomsuq
  108  plqsccvgrg¬uspcgoxf↔,x∧usdfmmnuuckjjfkqpukkwqyuusxxyss¬¬jjwp
  108  m¬whyx¬wpccukf)[,'!|9*344555551Hyspwajkcvvcvb∃*2cufmh)3645vnI6
  108  *26\≥*2pVg6 [7cn hhsu∧bv¬snfocmulas was established 
  113  _rst, in independdfo studkussbxsJ∧mnnF),Fk¬bnnukffHakfsA*2,He
  116  ul∧jgnn.,Dk¬bnn[[≥↑*2 NuxxbjcThebg¬s|π]≡**/(*57(, 
  118  i41*?*?*?*?ixon [|εJ. Number Theory |π|≡2 (1970), 
  124  414<422] developed the theory of the |εF|βn(x) 
  131  |πdistributions to show that individual partial 
  137  quotients are essentially independent of each 
  143  other in an appropriate sense, and proved that 
  151  for all positive |ε|≤o |πwe have |¬G|εT(m,|4n)|4α_↓|4|≥1(12|
  157  4|πln|42)/|ε|≤p|g2)|4|πln|4|εn|¬G|4|¬W|4(|πln|4|εn)|g(|g1|g/
  157  |g2|g)|gα+↓|g|≤o |πexcept for exp(|ε|→α_↓c(|≤o)(|πlog|4|εN)|
  160  g|≤o|g/|g2)N|g2 |πvalues of |εm, n |πin the range 
  168  |ε1|4|¬E|4m|4|¬W|4n|4|¬E|4N, |πwhere |εc(|≤o)|4Q|40. 
  171  |πHeilbronn's approach was completely di=erent, 
  176  working entirely with integers instead of continuous 
  183  variables. His idea, which is prjsented in slightly 
  191  modi_ed form in exercises 33 and 34, is based 
  200  on the fact that |ε|≤t|βn |πcan be related to 
  209  the number of ways to represent |εn |πin a certain 
  219  manner. Furthermore, his paper [|εNumber Theory 
  225  and Analysis, |πed. by Paul Tur|=1an (New York: 
  233  Plenum, 1969), 87<96] shows that the distribution 
  240  of individual partial quotients 1, 2,|4.|4.|4. 
  246  which we have discussed above actually applies 
  253  to the entire collection of partial quotients 
  260  belonging to the fractions havicvvuugivenndenominator; 
  265  this is a sharper form of Theorem E. A still 
  275  sharper result was obtained several years later 
  282  by J. W. Porter |ε[Mathematika |π|≡2|≡2 (1975), 
  289  20<28], who established that |ε|≤t|βn|4α=↓|4|≥1(12|4|πln|42)
  293  /|ε|≤p|g2)|4|πln|4|εn|4α+↓|4C|4α+↓|4O(n|gα_↓|g1|g/|g6|gα+↓|g
  293  |≤o|≥2, |πwhere |εC|4α=↓|41.4670780794|4.|4.|4. 
  296  |πcan be expressed as a complicated combination 
  303  of sums and integrals. Thus the conjecture (47) 
  311  is fully proved.|'{A6}!|9|4|1|1|1We can also 
  317  estimawte the9|4|1|1|1We can also estimate the 
  323  average number of division steps when |εu |πand 
  331  |εv |πare both uniformly distributed between 
  337  1 and |εN, |πby calculating|'{A6}|(|ε1|d2N|)|4|↔k|uc|)1|¬En|
  342  ¬EN|)|4T|βn.|J!(54)|;{A6}|πAssuming formula (52), 
  346  this sum has the form|'{A6}|(|π12|4ln|42|d2|ε|≤p|g2|)|4|πln|
  351  4|εN|4α+↓|4O(1),|J!(55)|;{A6}|π(see exercise 
  354  27), and empirical calculations with the same 
  361  numbers used to derive Eq. 4.5.2<45 show good 
  369  agreement with the formula|'{A6}|ε|(|π12|4ln|42|d↑6ε|≤p|g2|)
  373  |4|πln|4|εN|4α+↓|40.06.|J!(56)|;{A6}!|9|4|1|1|1|πThe 
  375  average running time for Euclid's algorithm on 
  382  multiprecision integers, using classical algorithms 
  387  for arithmetic, was shown to be of order |≥11|4α+↓|4log(max(
  395  |εu,|4v)/|πgcd(|εu,|4v)|≥2|≥2|1|1|πlog|4min(|εu,|4v) 
  396  |πby G. E. Collins, |εSIAM J. Computing |π|≡3 
  404  (1974), 1<10.|'|'|≡*3|≡u|≡m|≡m|≡a|≡r|≡y|≡.|9|4We 
  408  have found that the worst case of Euclid's algorithm 
  417  occurs when its inputs |εu and |εv |πare consecutive 
  426  Fibonacci numbers (Theorem F); the number of 
  433  division steps when |εv|4α=↓|4n |πwill never 
folio 468 galley 2
  439  exceed |"p4.8|4log|β1|β0|4|εN|4α_↓|40.32|"P. 
  441  |πWe have determined the freqqufcy of the values 
  449  of various partial quotients, showing, for example, 
  456  that the division step _nds |"l|εu/v|"L|4α=↓|41 
  462  |πabout 41 percent of the time (Theorem E). And, 
  471  _nally, the theorems of Heilbronn and Dixon show 
  479  that the average number |εT|βn |πof division 
  486  steps when |εv|4α=↓|4n |πis approximately|'{A6}|π(12|4{U0}{H
  491  10L12M29}|πW58320#Computer Programming!ch. 4!f. 
  494  468!g. 2|'{A6}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'|'
  498  {H9L11}|9|1|≡1|≡.|9|4[|*/|↔P|↔c|\]|9|πSince the 
  500  quotient |ε|"lu/v|"L |πis equal to unity over 
  507  40 percent of the time, it may be advantageous 
  516  on some computers to make a test for this case 
  526  and to avoid the division when the quotient is 
  535  unity. Is the following |¬m|¬i|¬x program for 
  542  Euclid's algorithm more e∃cient than Program 
  548  4.5.2A?|'{A6}|h|∂|9|1|1|9|1|1!|∂|9|1|1|9|1|1|9|1|1|9|1|1!|∂|
  549  9|1|1|9|1|1!!|∂|εrX|4|¬L|4rAX|4|πmod|4|εv.|9|E|n|;
  550  |L|L|π|¬l|¬d|¬x|L|¬u|LrX|4|¬L|4|εu.>|L|L|π|¬j|¬m|¬p|L|¬2|¬f|
  551  L>|L|¬1|¬h|L|¬s|¬t|¬x|L|¬v|L|εv|4|¬L|4|πrX.>|L|L|¬s|¬u|¬b|L|
  553  ¬v|LrA|4|¬L|4|εu|4α_↓|4v.>|L|L|π|¬c|¬m|¬p|¬a|L|¬v>
  555  |L|L|¬s|¬r|¬a|¬x|L|¬5|LrAX|4|¬L|4rA.>|L|L|¬j|¬l|L|¬2|¬F|LIs|
  556  4|εu|4α_↓|4v|4|¬W|4v?>|L|L|π|¬d|¬i|¬v|L|¬v|LrX|4|¬L|4rAX|4mo
  557  d|4|εv.>|L|π|¬2|¬h|L|¬l|¬d|¬a|L|¬v|LrA|4|¬L|4|εv.>
  559  |L|L|π|¬j|¬x|¬n|¬z|L|¬1|¬b|LDone if rX|4α=↓|40.>
  562  {A6}|9|1|≡2|≡.←9|4[|εM|*/|↔P|↔O|\]|9|πEvaluate 
  563  the matrix product|'{A6}|↔a|(|εx|β1|d51|)!|(1|d50|)|↔s|↔a|(x
  566  |β2|d51|)!|(1|d50|)|↔s|4αo↓|4αo↓|4αo↓|4|↔a|(x|βn|d51|)!|(1|d
  566  50|)|↔s.|;{A6}|π|9|1|≡3|≡.|9|4[|εM|↔P|↔O]|9|πWhat 
  568  is the value of|'{A6}|ε|h|∂|πdet!|4|∂|→α_↓1$|∂|→α_↓1!|∂|→α_↓
  572  1!|∂←→α_↓1!|∂0!|9|∂|E|n|;|>|;|9|4|εx|β1|'|9|41|'
  577  |9|40|'αo↓|4αo↓|4αo↓|'0|'>{A2}|>|'|→α_↓1|'|9|4xSβ2|'
  585  |9|41|'|'0|'>{A2}|>|'|9|40|'|→α_↓1|'|9|4x|β3|'
  594  |9|41|'|1|1αo↓|'>|>|πdet|'|'|'|'|'|1|1αo↓|'>|>
  606  |'|'|'←→α_↓1|'|'|1|1αo↓|'>|>|'|'|'←'←'1|'>{A2}|>
  620  |'|9|40|'|9|40|'.|4.|4.←'|→α_↓1←'|εx|β,|'>{A6}|9|1|π|≡5|≡.|9
  625  |4[|εHM|*/|↔P|↔C|\]|9|πLet |εx|β1, x|β2,|4.|4.←4. 
  628  |πbe a sequefce ofsreal numberf which are each 
  636  greater than some positive real number |ε|≤e) 
  643  |πProve that the in_nite continued fraction |"C|εx|β1,|4x|β2
  649  ,|4.|4.|4.|"C|4α=↓|4|πlim|ε|βn|1|β|¬XN1←β|¬XF1|1|"CxFβ1,←4.]
  649  4#]4.|4,]4)|βn|"6 |πexists. Show also that |"C|εx|β1,|4x|β2,
  654  |4.|4.|4.|"C |πneed not exist if we assume only 
  662  that |εx|βj|4|¬Q|40 |πfor all |εj.|'{A3}|9|1|π|≡6|≡.|9|4[|εM
  667  |*/|↔P|↔L|\]|9|πProve that the regular continued 
  672  fraction expansion expansion of a nuxber is |εunique 
  680  |πin the following sense: If |εB|β1, B|β2,|4.|4.|4. 
  687  |πare positive integers,λthen thesin_nitescontinued 
  691  frjkoion |"CNεB|β1,]4B|β2,|4.|4.|4.|"C |πis an 
  695  irrational number |εX |πbetweef 0 andn1λwhofe 
  701  rd∧kwar conoinuedffkjction has |εA|βn|4α=↓|4B|βn 
  705  |πfor all |εn|4|¬R|41; |πand if |εB|β1,|4.|4.|4.|4,|4B|βm 
  711  |πare positive integers with |εB|βm|4|¬Q|41, 
  716  |πthen the regular continued fjaction forn|εXN4(*244.7}Xi1,N4
  721  #.47.4#[4/]4XivM.6c|π.aus|≥%UβcN4≡↓*44αFicn|π↔brc|≥*544←¬DS4/N
  721  44¬DS4#.M,{{3}o|9|1|≡7|≡.]9:4[[N*/←↔P|↔o|\]|9|π*4indsall 
  722  pqjv¬qazionfs|εp(1)*45∀(2)←4.N4.N4#[4∀(n) |πof 
  724  |¬T1,|42,|4.]4.|4.←4,|4|εn|¬Y |πsuch that |εQ|βn(x|β1,]4x|β2
  727  ,←4.]4#]4.|4,]4*2Sβn)*44α≡↓|4\Sβn()|βp|β(|β1←β), 
  728  x|βp|β(Nβ2|β),|4.←4.]4.←4,λxFβp|β(|βn|β)) |πholds 
  730  for awl |εxFβ1,λx|β2,←4.]4.|4.|4,|4x|βn.|'{A3}|:*35←≡8*3≡)]9*34
  733  [[N*/*3↔5|↔≡C\]|9*3πIf |εXSβn |π∪ssde_ned↔λin the 
  737  re∧ular continued fraction process, show that 
  743  |"C|εA|βn,|4.|4.|4.|4,←4A|β1,λ|→α_↓X|"6|4α=↓|4|→α_↓1/X|βn.|'
  744  {A3}|9|14≡α|≡)[::4⊗[NεN*/*3↔\|*4αN\**]9*3π*4yo∧sthaw 
  745  cvnmickudffkjkgignfssazisfysthe following identities:|'
  748  !!|5←1_*2*4::55[7C\*2Xi1#]4#[47[4#[4,]4XIcN.6C4*2↓←4←.7¬Fβ1,]4#[
  748  4#]4#[4/]4XikF4α~↓**44"6¬XIkKi↓~↓β1,]4#[4.[4#[4/]4)|βnN"6|"C,
  748  !!1|4|¬E|4k|4|¬E|4n;|'!!|1414πα)(::.7C≥*5,]4*2Xi1#]4*2Fβ2/]4#[4
  749  #[4#]4/]4*2SβnN"6|4α=↓|4)Fβ1←4α+↓|4←"6xFβ2/]47[4#[4#]4/]4*2Xic
  749  N.76]!NN44}}C45\:]'!!|5555[/*2(::5555\\[7}XI1#]47[47[47[46]4X
  749  IkKI↓↓↓I17]4XIk≡]45[]4*2XikKI↓α↓i17]4XikKi↓~↓I26]47[4#[4#[4/]
  749  4XIcN"6C]'|[7}XI17]47[47[47[46]44xXIkKi↓≠↓**β1/]4XIkF4~↓4)Nβk
  749  KI↓~↓*4β1/]4*2FβkKi↓~↓**β2,]4#]4#]47[4/]4*2FicN[76]!1544}}C4**K44
  749  }}Q46):*3?!!|5514π-)*49:\*544α≠↓**44.6¬Sβ16]4*2Fβ2,]4.]4.←4.]4/]4
  749  )SβcN[7C4≡**44[777]4XI154≤↓457]4XI26]47[4#[4#[46]4XIcN.7/]!nN
  749  4←¬}C45#],{A↓}|[]**5≡→***2[::47]≥M*/*/↔I↔≤I\]:*3[αxsthesrjsuwl 
  750  mffsxdjccses6,λe¬jj¬sirrjwionjwpcjawink¬xbjc|≥X|[[qusuuukcqq
  750  uscj∧¬qwjccvmmpckudffkjkction represent*?*?*?continued 
  752  fraction representation of the form|'{A6}|εX|4α=↓|4A|β0|4α+↓
  757  |4|"CA|β1,|4A|β2,|4A|β3,|4.|4.|4.|"C,|;{A6}|πwhere 
  759  |εA|β0 |πis an integer and |εA|β1, A|β2, A|β3,|4.|4.|4. 
  767  |πare positive integers. Show that if |εX |πhas 
  775  this representation then the regular continued 
  781  fraction for |ε1/X |πis|'{A6}|ε1/X|4α=↓|4B|β0|4α+↓|4|"CB|β1,
  785  |4.|4.|4.|4,|4B|βm,|4A|β5,|4A|β6,|4.|4.|4.|"C|;
  786  {A6}|πfor suitable integers |εB|β0, B|β1,|4.|4.|4.|4, 
  791  B|βm. |π(This case |εA|β0|4|¬W|40 |πis of course 
  798  the most interesting.) Explain how to determine 
  805  the |εB'|πs in terms of |εA|β0, A|β1, A|β2, A|β3, 
  814  |πand |εA|β4.|'{A3}|≡1|≡1|≡.|9|1[M|*/|↔L|↔c|\]|9|π(J. 
  817  Lagrange.))PWt |εX|4α=↓|4A|β0|4α+↓|4|"CA|β1,|4A|β2,|4.|4.|4.
  818  |"C, Y|4α=↓|4B|β0|4α+↓|4|"CB|β1,|4B|β2,|4.|4.|4.|"C 
  820  |πbe the regular continued fraction representations 
  826  of two real numbers |εX |πand |εY, |πin the sense 
  836  of exercise 10. Show that these representations 
  843  ``eventually agree,'' in the sense that |εA|βm|βα+↓|βk|4α=↓|
  849  4B|βn|βα+↓|βk |πfor some |εm |πand |εn |πand 
  856  for all |εk|4|¬R|40, |πif and only if |εX|4α=↓|4(qY|4α+↓|4r)
  863  /(sY|4α+↓|4t) |πfor some integers |εq, r, s, 
  870  t |πwith |ε|¬Gqt|4α_↓|4rs|¬G|4α=↓|41. |π(This 
  874  theorem is the analog, for continued fraction 
  881  representations, of the simple result that the 
  888  representations of |εX |πand |εY |πin the decimal 
  896  system eventually agree if and only if |εX|4α=↓|4(10|gqY|4α+
  903  ↓|4r)/10|gs |πfor some integers |εq, r, |π≠fd 
  910  |εs.)|'{A3}|ε|≡1|≡2|≡.|9|4[M|*/|↔L|↔c|\]|9|πA 
  912  |εquadratic irrationality |πis a number of the 
  919  form (|ε|¬H|v4D|)|4α_↓|4U)/V, |πwhere |εD, U, 
  924  |πand |εV |πare integers, |εD|4|¬Q|40, V|4|=|↔6α=↓|40, 
  930  |π_fds|εD |πis noo a perfeco square. We may assume 
  939  without loss of generality that |εV |πis a divisor 
  948  of |εD|4α_↓|4U|g2, |πfor otherwise the number 
  954  may be rewritten as (|}¬H|v*?*?e nkmber may be 
  962  rewritten as (|¬H|v4|εDV{J.5}|g2|)|4α_↓|4U|1|1|¬GV|¬G)/V|1|1
  964  |¬GV|¬G.|'!!|1|1|πa)|9Prove that the regular 
  969  continued fraction expansion (in the sense of 
  976  exercise 10) of a quadratic irrationality |εX|4α=↓|4(|¬H|v4D
  982  |)|4α_↓|4U)/V |πis obtained by the following 
  988  formulas:|'{A6}|εV|β0|4α=↓|4V,!!A|β0|4α=↓|4|"lX|"L,!!U|β0|4α
  989  =↓|4U|4α+↓|4A|β0V;|;V|βn|βα+↓|β1|4α=↓|4(D|4α_↓|4U|1|=|βn|g2)
  990  /V|βn,!!A|βn|βα+↓|β1|4α=↓|4|"l(|¬H|v2D|)|4α+↓|4U|βn)/V|βn|βα
  990  +↓|β1|"L,|;{A4}U|βn|βα+↓|β1|4α=4*/|βn|βα+↓|β1V|βn|βα+↓|β1|4α_
  991  ↓|4U|βn.|;{A6}|π[|εNote|*/:|\ |πAn algorithm based 
  996  on this process has many applications to the 
 1004  solution of quadratic equations in integers; 
 1010  see, for example, H. Davenport, |εThe higher 
 1017  arithmetic (|πLondon: Hutchinson, 1952); W. J. 
 1023  LeVeque, |εTopics in Number Theory (|πReading, 
 1029  Mass.: Addison-Wesley, 1956); and see Section 
 1035  4.5.4. By exercise 1.2.4<35, |εA|βn|βα+↓|β1|4α=↓|4|"l(|"l|¬H
 1039  |v4D|)|1|"L|4α+↓|4U|βn)/V|βn|βα+↓|β1|"L |πwhen 
 1041  |εV|βn|βα+↓|β1|4|¬Q|40, |πand |εA|βn|βα+↓|β1|4α=↓|4|"l(|"l|¬
 1043  H|v4D|)|"L|4α+↓|41|4α+↓|4U|βn)/V|βn|βα+↓|β1|"L 
 1044  |πwhen |εV|βn|βα+↓|β1|4|¬W|40; |πhence such an 
 1049  algorithm need only work qqph the integer |"l|ε|¬H|v4D|)|1|"
 1056  L.]|'|π!!|1|1b)|9Prove that |ε0|4|¬W|4U|βn|4|¬W|4|¬H|v4D|)|1
 1059  , 0|4|¬W|4V|βn|4|¬W|42|¬H|v4D|)|1, |πfor all 
 1063  |εn|4|¬Q|4N, |πwhere |εN |πis some integer depending 
 1070  on |εX; |πhence the regular continued fraction 
 1077  representation of every quadratic irrationality 
 1082  is eventually periodic. [|εHint|*/:|\ |πShow that 
 1088  (|→α_↓|ε|¬H|v4D|)|4α_↓|4U)/V|4α=↓|4A|β0|4α+↓|4|"CA|β1,|4.|4.
 1088  |4.|4,|4A|βn, |→α_↓V|βn/(|¬H|v4D|)|4α+↓|4U|βn)|"C, 
 1090  |πand use Eq. (5) to prove that (|ε|¬H|v4D|)|4α+↓|4U|βn)/V|β
 1097  n |πis positive when |εn |πis large.]|'!!|1|1c)|9|1|1Letting
 1104   |εp|βn|4α=↓|4Q|βn|βα+↓|β1(A|β0,|4A|β1,|4.|4.|4.|4,|4A|βn) 
 1106  |πand |εq|βn(A|β1,|4.|4.|4.|4,|4A|βn), |πprove 
 1109  that |εVp|=|βn|g2|4α+↓|42Up|βnq|βn|4α+↓|4|≥1(U|g2|4α_↓|4D)/V
 1110  |1)q|=|βn|g2|4α=↓|4(|→α_↓1)|gn|gα+↓|g1V|βn|βα+↓|β1.|'
 1111  !!|1|1|πd)|9PVrove hqz thesrdgular continued 
 1115  fraction representation of an irrational number 
 1121  |εX |πis eveftually periodic if and only if |εX 
 1130  |πis a quadratic irrationality. (This is the 
 1137  continued fraction analog of the fact that the 
 1145  decimal expansion of a real number |εX |πis eventually 
 1154  periodicnif afdfongqsif |ε(f|πcs rjwionjl#)(,{J3d|≡1←≡3←≡.]9
 1157  *3ε[M|*/|↔M|↔c|\*4]9(*3πJ.λLagrange, 1797.)↔Let |εf(x)|4α=↓|4a|β
 1159  nx|gn|4α+↓|4αo↓|4αo↓|4α↓|4α+↓|4a|β0,|4a|βn|4|¬Q|40, 
 1160  |πbe a polynomial with integer coe∃cients, having 
 1167  no rational roots, and having exactly one real 
 1175  root |ε|≤j|4|¬Q|41. |πDesign a computer program 
 1181  to _nd the _rst thousand or so partial quotientssnof 
 1190    ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 1192  |||||||||||||||||||||||||||||||||||||||||||||||||||||||*?*?enm
 1192  ysof |ε|≤j, |πusing the following algorithm (which 
 1199  involves only multiprecision addition).|'{A6}{I1.6H}|≡L|≡1|≡
 1203  .|9Set |εA|4|¬L|41.|'|π|≡L|≡2|≡.|9For |εk|4α=↓|40,|41,|4.|4.
 1206  |4.|4,|4n|4α_↓|41 (|πin this order), and for 
 1212  |≥≤|4α=↓|4n|4α_↓|41,|4.|4.|4.|4,|4k |π(in this 
 1215  order) set |εa|βj|4|¬L|4a|βj|βα+↓|β1|4α+↓|4a|βj. 
 1218  |π(This step replaces |εf(x) |πby |εg(x)|4α=↓|4f(x|4α+↓|41),
 1223   |πa polynomial whose roots are one less than 
 1232  those of |εf.)|'{A3}|π|≡L|≡3|≡.|9If |εa|βn|4α+↓|4a|βn|βα_↓|β
 1236  1|4α↓|4αo↓|4αo↓|4αo↓|4α+↓|4a|β0|4|¬W|40, |πset 
 1238  |εA|4|¬L|4A|4α+↓|41 |πand return to L2.|'{A3}|≡L|≡4|≡.|9Outp
 1243  ut |εA (|πwhich is the value of the next partial 
 1253  quotient). Replace (|εa|βn,|4a|βn|βα_↓|β1,|4.|4.|4.|4,|4a|β0
 1255  ) |πby |ε(|→α_↓a|β0,|4|→α_↓a|β1,|4.|4.|4.|4,|4|→α_↓a|βn) 
 1258  |πand return to L1. (This step replaces |εf(x) 
 1266  |πby a polynomial whose roots are reciprocals 
 1273  of those of |εf.)|'{A6}{IC}t|πFor example, starting 
 1280  with |εf(x)|4α=↓|4x|g3|4α_↓|42, |πthe algorithm 
 1284  will output 1 (changing |εf(x) |πto |εx|g3|4α_↓|43x|g2|4α_↓|
 1290  43x|4α_↓|41); |πthen 3 (changing |εf(x) |πto 
 1296  |ε10x|g3|4α_↓|46x|g2|4α_↓|46x|4α_↓|41); |πetc.|'
 1298  {A3}|≡14≡4←≡.←9*34←ε[MN*/←↔P|↔|\]|9←π(↑. Hurwutz, 
 1300  1891.) Showsthat the following rules make it 
 1307  possible to _nd the regular continued fraction 
 1314  expansion for |ε2X, |πgiven the partial quotientssof 
 1321  |εX:*3'↓J6}2|"C2a,|4b,|4c,|4.|4.|4.|"C|4α=↓|4|"Ca,←42b|4α+↓|4
 1321  2|"Cc,|4.|4.←4.|"C|"C;|;{A4}2|"C2_|4α+↓|41,]4b,|4c,←4.←4.←4#
 1322  ]"6|4α=↓|4←"6a,←41,|41|4α+↓|426|"CCCCCCCCCCCCCCCCCVC}C}C}C∧}
 1322  b¬bbbbbbb*?*?*?"Ca↔|41,|41|4α+↓|42|"Cb|4α_↓|41,|4c,|4.|4.|4.|"C
 1322  |"C.|;{A6}|πUse this idea to _nd the regular 
 1330  continued fraction expansion of |ε|f1|d32|)e, 
 1335  |πgiven the expansion of |εe |πin (13).|'{A3}|≡1|≡5|≡.|9|ε[M
 1342  |*/|↔L|↔O|\]|9|π(R. W. Gospen.) Generalizing exercise 
 1347  14, design an algorithm which computes the continued 
 1355  fraction |εX|β0|4α+↓|4|"CX|β1,|4X|β2,|4.|4.|4.|"C 
 1357  |πfor |ε(ax|4α+↓|4b)/(cx|4α+↓|4d), |πgiven the 
 1361  continued fraction |εx|β0|4α+↓|4|"Cx|β1,|4x|β2,|4.|4.|4.|"C 
 1364  |πfor |εx, |πand given integers |εa, b, c, d 
 1373  |πwith |εad|4|=|↔6α=↓|4bc. |πMake your algorithm 
 1378  an ``on-line coroutine'' which outputs as many 
 1385  |εX|βk |πas possible before inputting each |εx|βj. 
 1392  |πDemonstrate how your algorithm computes |ε(97x|4α+↓|439)/(
 1397  |→α_↓62x|4α_↓|425) |πwhen |εx|4α=↓|4|→α_↓1|4α+↓|4|"C5,|41,|4
 1399  1,|41,|42,|41,|42|"C.|'{A3}|π|≡1|≡6|≡.|9|4|ε[HM|*/|↔L|↔c|\]|9
 1400  (|ε|πL. Euler, 1731.) Let |εf|β0(z)|4α=↓|4(e|gz|4α_↓|4e|gα_↓
 1404  |gz)/(e|gz|4α+↓|4e|gα_↓|gz)|4α=↓|4|π+anh|4|εz, 
 1405  |πand let |εf|βn|βα+↓|β1(z)|4α=↓|41/f|βn(z)|4α_↓|4(2n|4α+↓|4
 1407  1)/z. |πProve that, for all |εn, f|βn(z) |πis 
 1415  an analytic function of the complex variable 
 1422  |εz |πin a neighborhood of the ogcgin, and it 
 1431  satis_es the di=erential equation |εf|1|=|βnαO↓(z)|4α=↓|41|4
 1435  α_↓|4f|βn(z)|g2|4α_↓|42nf|βn(z)/z. |πUse this 
 1438  fact to prove that|'{A6}tanh|4|εz|4α=↓|4|"Cz|gα_↓|g1,|43z|gα
 1442  _↓|g1,|45z|gα_↓|g1,|47z|gα_↓|g1,|4.|4.|4.|"C.|;
 1443  {A6}|πThen apply Hujwitz's rule (exercise 14) 
 1449  to prove that|'{A6}|εe|gα_↓|g1|g/|gn|4α=↓←4←"C|v21,|4(2m|4α+
 1452  ↓|41),|4α_↓|41,|41|)|"C,!!m|4|¬R|40.|;{A6}|π(This 
 1454  notation denotes the in_nite continued fraction 
 1460  |"C1,|4n|4α_↓|41,|41,|41,|43|εn|4α_↓|41,|41,|41,|45n|4α_↓|41
 1460  ,|41,|4.|4.|4.|"C.) |πAlso _nd the regular continued 
 1466  fraction expansion for |εe|gα_↓|g2|g/|gn |πwhen 
 1471  |εn|4|¬Q|40 |πis odd.|'{A3}|≡1|≡7|≡.|9|4|ε[M|*/|↔P|↔L|\]|9(a)
 1474   |πProve that |ε|"Cx|β1,|4|→α_↓x|β2|"C|4α=↓|4|"Cx|β1|4α_↓|41
 1477  ,|41,|4x|β2|4α_↓|41|"C. |π(b) Generalize this 
 1481  identity, obtaining a formula for |ε|"Cx|β1,|4|→α_↓x|β2, 
 1487  x|β3, |→α_↓x|β4,|4.|4.|4.|4, x|β2|βn|βα_↓|β1, 
 1490  |→α_↓x|β2|βn|"C |πin which all partial quotients 
 1496  are positive integers when the |εx'|πs |πare 
 1503  large positive integers. (c) The result of exercise 
 1511  16 implies that tan|41|4α=↓|4|"C1,|4|→α_↓3,|45,|4|→α_↓7,|4.|
 1514  4.|4.|"C. Find the regular continued fraction 
 1520  exp{U0}{H10L12M29}|πW58320#Computer Programming!ch. 
folio 473 galley 3
 1522  4!f. 473!g. 3|'{A6}{H9L11}|π|≡1|≡8|≡.|9|4|ε[M|*/|↔M|↔c|\]|9|π
 1525  Develop a computer program to _nd as many partial 
 1534  quotients as possible of a real number given 
 1542  with high precision. Use this program to calculate 
 1550  the _rst one thousand (or so) partial quotients 
 1558  of Euler's constant |ε|≤g, |πbased on D. W. Sweeney's 
 1567  3566-place value |ε[Math. Comp. |π|≡1|≡7 (1963), 
 1573  170<178]. (Note that we expect to get about 0.97 
 1582  partial quotients per decimal digit. Cf. Algorithm 
 1589  4.5.2L and the article by J. W. Wrench, Jr. and 
 1599  D. Shanks, |εMath. Comp. |π|≡2|≡0 (1966), 444<447.)|'
 1606  {A3}|≡1|≡9|≡.|9|4|ε[M|*/|↔P|↔c|\]|9|π7Vgve that 
 1608  |εF(x)|4α=↓|4|πlog|ε|βb(1|4α+↓|4x) |πsatis_es 
 1610  Eq. (24).N'{A3}|≡2|≡0|≡.|9|4|ε[HM|*/|↔P|↔c|\]|9|πDerive 
 1612  (36) from (35).|'{A3}|≡2|≡1|≡.|9|4|ε[HM|*/|↔P|↔m|\]|9(|πE. 
 1616  Wirsing.) The bounds (37) were obtained for a 
 1624  function |ε|≤' |πcorresponding to |εg |πwith 
 1630  |εTg(x)|4α=↓|41/(x|4α+↓|41). |πShow that the 
 1634  function which corresponds to |εTg(x)|4α=↓|41/(x|4α+↓|4c) 
 1639  |πyields better bounds, when |εc|4|¬Q|40 |πis 
 1645  an appropriate constant.|'{A3}|≡2|≡2|≡.|9|4[|εHM|*/|↔M|↔p|\]|
 1648  9|π(E. Wirsing.) Find another term in the asymptotic 
 1656  expansion of |εF|βn(x), |πimproving on (38).|'
 1662  {A3}|≡2|≡3|≡.|9|4|ε[HM|*/|↔P|↔L|\]|9|πProve (50), 
 1664  using results from the proof of Theorem W.|'{A3}|≡2|≡4|≡.|9|
 1672  4|ε[M|*/|↔P|↔P|\]|9|πWhat is the average value 
 1677  of a partial quotient |εA|βn |πin the regular 
 1685  continued fraction expansion of a random real 
 1692  number?|'{A3}|≡2|≡5|≡.|9|4|ε[HM|*/|↔P|↔C|\*4]9←πFind 
 1694  an example of a set |ε|λi|4α=↓|4I|β1|4|↔q|4I|β2|4|↔q|4I|β3|4
 1699  |↔q|4αo↓|4αo↓|4αo↓|4|↔Y|4[0,|41], |πwhere the 
 1702  |εi'|πs are disjocnt intervals, for which (42) 
 1709  does not hold.|'{A3}|≡2|≡6|≡.|9|4|ε[M|*/|↔P|↔L|\]|9|πShow 
 1713  that if the numbers |ε1/n, 2/n,|4.|4.|4.|4, |"ln/2|"L/n 
 1720  |πare expressed as regular continued fractions, 
 1726  the result is symmetric between left and right, 
 1734  in the sense that |"C|εA|βt,|4.|4.|4.|4,|4A|β2,|4A|β1|"C 
 1739  |πappears whenever |ε|"CA|β1,|4A|β2,|4.|4.|4.|4,|4A|βt|"C 
 1742  |πdoes.|'{A3}|≡2|≡7|≡.|9|4|ε[M|*/|↔P|↔O|\]|9|πDerive 
 1744  (52) from (46) and (51).|'{A3}|≡2|≡8|≡.|9|4|ε[M|*/|↔P|↔L|\]|9
 1749  |πProve the following identities involving the 
 1755  three number-theoretical functions |ε|≤'(n), 
 1759  |≤m(n), |*/|≤!|\(n):|'|π!!|1|1a)|9|1|↔k|uc|)|εd|¬Dn|)|4|≤m(d)
 1761  |4α=↓|4|≤d|βn|β1.!!!!|πb)|9ln|4|εn|4α=↓|4|↔k|uc|)d|¬Dn|)|4|*/
 1761  |≤!|\(d),!!n|4α=↓|4|↔k|uc|)d|¬Dn|)|4|≤'(d).|'
 1762  {A4}!!|1|1|πc)|9|1|1|ε|*/|≤!|\(n)|4α=↓|4|↔k|uc|)d|¬Dn|)|4|≤m|
 1762  ↔a|(n|d2d|)|↔s|4|πln|4|εd,!!|≤'(n)|4α=↓|4|↔k|uc|)d|¬Dn|)|4|≤
 1762  m|↔a|(n|d2d|)|↔s|1|1d.|'{A6}|π|≡2|≡9|≡.|9|4|ε[M|*/|↔P|↔L|\]|9
 1763  |πAssuming that |εT|βn |πis given by (52), show 
 1771  that (54)|4α=↓|4(55).|'{A3}|π|≡3|≡0|≡.|9|4|ε[HM|*/|↔L|↔P|\]|9
 1773  |πThe following modi_cation of Euclid's algorithm 
 1779  is often suggested: Instead oxfnrepwcing |εv 
 1785  |πby |εu|4|πmod|4|εv |πduring the division step, 
 1791  replace it by |¬G(|εu|4|πmod|4|εv)|4α_↓|4v|¬G 
 1795  |πif |εu|4|πmod|4|εv|4|¬Q|4|f1|d32|)v. |πThus, 
 1798  for exjmvle, if |εu|4α=↓|426 |πand |εv|4α=↓|47, 
 1804  |πwe have gcd|4(26,|47)|4α=↓|4gcd|4(|→α_↓2,|47)|4α=↓|4gcd|4(
 1806  7,|42); |→α_↓2 |πis the remainder of smallest 
 1813  magnitude when multiples of 7 are subtracted 
 1820  from 26. Compare this procedure with Euclid's 
 1827  algorithm; estimate the number of division steps 
 1834  this method saves, on the av¬jj∧e.|'{A3}|≡3|≡1|≡.|9←4|ε[[|*/*3
 1840  ↔1|↔**C\*4]9*3π*4und thes``≤brfz case-',of thesmodi_≡ation 
 1844  of Euclid'? algorithm su∧gestedfin exejccues3π;?wyaz 
 1849  ard thyssx∧llesyhinvuty |ε≥U44¬}Y4#V44¬Q|41λ|πwhicm 
 1852  requurds|ε↔ |π-uvisugn szeps?←'{A3}|≡3|≡2←≡.|9|4←ε[|*/|↔|↔cN\
 1854  ]|9|π(a) AsMorse codessequefcdsofslefgth |εn 
 1858  |πis a string of |εr |πdots and |εs |πdashes, 
 1867  where |εr|4α+↓|42s|4α=↓|4n. |πFor example, the 
 1872  Morse code sequences of length 4 are|'{A6}αo↓|4αo↓|4αo↓|4αo↓
 1879  |4,|4αo↓|4αo↓|4#|4,|4αo↓|4#|4αo↓|4,|4#|4αo↓|4αo↓|4,|4#|4#|;
 1880  {A6}|πNoting thawhhhesconmpckafo pvgqxmmcawp|ε\Sβ4)Fβ1,]4)Fβ
 1882  2,|4xFβ3,|4x|β4)|4α=↓|4x|β1x|β2x|β3)|β4|4α∃↓|4xFβ1*2Fβ2←4~↓*34
 1882  xFβ1*2Xβ4←4αα+↓|*?*?*?|4α+↓|4x|β1x|β4|4α+↓|4x|β3x|β4|4α+↓|41, 
 1883  |π_nd and prove a simple relation between |εQ|βn(x|β1,|4.|4.
 1890  |4.|4,|4x|βn) |πand Morse code sequences of length 
 1897  |εn. |π(b) (L. Euler, |εNovi Comm. Acad. Sci. 
 1905  Pet. |π|≡9 (1762), 53<69.) Prove that |εQ|βm|βα+↓|βn(x|β1,|4
 1911  .|4.|4.|4, x|βm|βα+↓|βn)|4α=↓|4Q|βm(x|β1,|4.|4.|4.|4, 
 1913  x|βm)Q|βn(x|βm|βα+↓|β1,|4.|4.|4.|4, x|βm|βα+↓|βn)|4α+↓|4Q|βm
 1914  |βα_↓|β1(x|β1,|4.|4.|4.|4, x|βm|βα_↓|β1)Q|βn|βα_↓|β1(x|βm|βα
 1915  +↓|β2,|4.|4.|4.|4, x|βm|βα+↓|βn).|'{A3}|π|≡3|≡3|≡.|9|4|ε[M|*/
 1917  |↔L|↔P|\]|9|πLet |εh(n) |πbe the number of representations 
 1924  of |εn |πin the form|'{A6}|εn|4α=↓|4xx|¬S|4α+↓|4yy|¬S,!!x|4|
 1929  ¬Q|4y|4|¬Q|40, x|¬S|4|¬Q|4y|¬S|4|¬Q|40, |πgcd(|εx,|4y)|4α=↓|
 1931  41, |πinteger |εx, x|¬S, y, y|¬S.|;{A6}|π(a)|9Show 
 1938  that if the conditions are relaxed to allow |εx|¬S|4α=↓|4y|¬
 1946  S, |πthe number of representations is |εh(n)|4α+↓|4|"l(n|4α_
 1952  ↓|41)/2|"L. |π(b) Show that for _xed |εy|4|¬Q|40 
 1959  |πand |ε0|4|¬W|4t|4|¬E|4y, |πwhere gcd|ε(t,|4y)|4α=↓|41, 
 1963  |πand for each _xed |εx|¬S |πsuch that |εx|¬St|4|"o|4n 
 1971  |π(modulo |εy) |πand |ε0|4|¬W|4x|¬S|4|¬W|4n/(y|4α+↓|4t), 
 1975  |πthere is exactly one representation of |εn 
 1982  |πsatisfying the resyrictions of (a) and the 
 1989  condition x|4|"o|4t (modulo |εy). |π(c) Consequently|'
 1995  {A6}|εh(n)|4α=↓|4|↔k|4|↔d|↔a|(n|d2y|4α+↓|4t|)|4α_↓|4t|¬S|↔s|
 1995  1|(1|d2y|)|↔f|4α_↓|4|"l(n|4α_↓|41)/2|"L,|;{A6}|πwhere 
 1997  the sum is over all positive integers |εy, t, 
 2006  t|¬S |πsuch that gcd(|εt,|4y)|4α=↓|41, t|4|¬E|4y, 
 2011  t|¬S|4|¬E|4y, tt|¬S|4|"o|4n (|πmodulo |εy). |π(d) 
 2016  Show that each of the |εh(n) |πrepresentations 
 2023  can be expressed uniquely in the form|'{A6}|εx|4α=↓|4Q|βm(x|
 2030  β1,|4.|4.|4.|4,|4x|βm),!!y|4α=↓|4Q|βm|βα_↓|β1(x|β1,|4.|4.|4.
 2030  |4,|4x|βm|βα_↓|β1),|;{A4}x|¬S|4α=↓|4Q|βk(x|βm|βα+↓|β1,|4.|4.
 2031  |4.|4,|4x|βm|βα+↓|βk)d,!!y|¬S|4α=↓|4Q|βk|βα_↓|β1(x|βm|βα+↓|β
 2031  2,|4.|4.|4.|46,|4xxxxxxxxx*?*?*?*?k|βα_↓|β1(x|βm|βα+↓|β2,|4.|4.|
 2031  4.|4,|4x|βm|βα+↓|βk)d,|;{A6}|πwhere |εm, k, d, 
 2036  |πand the |εx|βj |πare positive integers with 
 2043  |εx|β1|4|¬R|42, x|βm|βα+↓|βk|4|¬R|42, |πand |εd 
 2047  |πis a divisor of |εn. |πThe identity of exercise 
 2056  32 now implies that |εn/d|4α=↓|4Q|βm|βα+↓|βk(x|β1,|4.|4.|4.|
 2060  4, x|βm|βα+↓|βk). |πConversely, every sequence 
 2065  of positive integers |εx|β1,|4.|4.|4.|4, x|βm|βα+↓|βk 
 2070  |πwith |εx|β1|4|¬R|42, x|βm|βα+↓|βk|4|¬R|42, 
 2073  |πand |εQ|βm|βα+↓|βk(x|β1,|4.|4.|4.|4, x|βm|βα+↓|βk) 
 2076  |πdividing |εn, |πcorresponds in this way to 
 2083  |εm|4α+↓|4k|4α_↓|41 |πrepresentations of |εn. 
 2087  |π(e) Therefore |εnT|βn|4α=↓|4|"l(5n|4α_↓|43)/2|"L|4α+↓|42h(
 2089  n).|'{A3}|≡3|≡4|≡.|9|4|ε[HM|*/|↔M|↔c|\]|9|π(H. 
 2091  Heilbronn.) (a) Let |εh|βd(n) |πbe the number 
 2098  of representations of |εn |πas in exercise 33 
 2106  such that |εxd|4|¬W|4x|¬S, |πplus half the number 
 2113  of representations with |εxd|4α=↓|4x|¬S. |πLet 
 2118  |εg(n) |πbe the number of representations without 
 2125  the requirement gcd|ε(x,|4y)|4α=↓|41. |πProve 
 2129  that|'{A6}|εh(n)|4α=↓|4|↔k|uc|)d|¬Dn|)|4|≤m(d)g|↔a|(n|d2d|)|
 2130  ↔s,!!g(n)|4α=↓|42|4|↔k|uc|)d|¬Dn|)|4h|βd|↔a|(n|d2d|)|↔s.|;
 2131  {A6}|π(b)|9Genejjwizing exdrcise 33b, show that 
 2136  fbr |εd|4|¬R|41, h|βd(n)|4α=↓|4|¬K|4(n/|≥1y(y|4α+↓|4t)|≥2|≥2
 2138  |4α+↓|4O(n), |πwhere the sum is over all integers 
 2146  |εy, t |πsuch that gcd|ε(t,|4y)|4α=↓|41, 0|4|}¬QI5|4|¬E|4y|4
 2151  |¬W|4|¬H|v4n/d|)|1.|'|π(c)|9|1|1Show that |¬K|4(||ε|≥1y/(y|4
 2154  α+↓|4t)|≥2|4α=↓|4|≤'(y)|4|πln|42|4α+↓|4|εO(|≤s|βα_↓|β1(y)|≥2
 2154  , |πwhere the sum iusover the range |ε0|4|¬W|4t|4|¬ES4y, 
 2162  |πgcd(|εt,|4y)|4α=↓|41; |πand |ε|≤s|βα_↓|β1(y)|4α=↓|4|¬K|4(|
 2164  βd|β|¬D|1|βy1/d).|'|π|π(d)|9Show that |¬K|ur|ε|)1|¬Ey|¬En|)|
 2167  ≤'(y)/y|g2|4α=↓|4|¬K|ur|)1|¬Ed|¬En|)|≤m(d)H|ur|)|"ln/d|"L|)/
 2167  d|g2.|'|π(e)|9|1Hefce |εT|βn|4α=↓|4(12|4|πln|42/|ε|≤∀|g2)|≥1
 2169  |πln|4|εn|4α_↓|4|¬K|βd|β|¬D|βn|*/|≤!|\(d)/d|≥2|4α+↓|4O(|≤s|βα
 2169  _↓|β1(n)|g2|≥2.←'{A3|π|≡3|≡5|≡.|9|4|ε[HM|*/|↔M|↔O|\]|9|π(A. 
 2170  Yao and D. E. Knuth.) Prove thaz the sux of all 
 2181  pajtial quotientssfbr the fractionf |εm/n,,p54|¬ES4m|4|¬W|4n
 2185  , |πis equal to 2(|¬K|4|"⊂|εx/y|"L|4α+↓N4←.∩n/2|"L),n|πwhere
 2189   the sum is over all representations |εn|4α=↓|4xx|¬S|4α+↓|4y
 2196  y|¬S |πsatisfying the conditions of exercise 
 2202  33(a). Show that |¬K|4|"l|εx/y|"L|4α=↓|43|≤p|gα_↓←g2n(|π⊂n|4
 2205  |ε↔)←g2]4α~↓|4O(,|4|πlog|4|εn(|πlog|4log|4|εn)|g2|≥2, 
 2206  |πand apply this to the ``_fcieno'',formnof Eucgids' 
 2213  algorithm which uses only subtraction instead 
 2219  of division.|'{A3}|≡3|≡6|≡.←9←4←ε[M|*/|↔L|↔C|\]|9|π(G.,H. 
 2222  Brad∧ey.)↔Wyaz iushhessxkwlwsz vjwqusoff|\≥Uicn|[)ukv 
 2225  hhqwhthescjwculwwivn ofsgcdSε(≡|β1,←4.|4.|4.←4,|4u|βn) 
 2227  |πby steps C1, C2 in Section 4.5.2 |π⊃equires 
 2235  |εN |πdivisions, if Euclid's algorithm is used 
 2242  throughout? Assumesthat |ε]|4|¬R|4/.←'{A3}|≡3|≡7|≡.|9|4|ε[M|
 2244  */|↔L|↔l|\]|9|π(T. S. Motzkin and E. G.λStraus.) 
 2250  Lez |ε_Si1,]4.]4.|4.←4,]4a|βn |πbe positive integers. 
 2255  Show that max|4|εQ|βn(a|βp|β(|β1|β),|4.|4.|4.|4, 
 2258  a|βp|β(|βn|β)), |πover all permutations |εp(1)|4αo↓|4αo↓|4αo
 2262  ↓|4p(n) |πof |ε|¬T1,|42,|4.|4.|4.[46]4n|¬Y, |πoccurs 
 2266  when |εa|βp|β(|β1|β)|4|¬R|4a|βp|β(|βn|β)|4|¬R|4a|βp|β(|β2|β)
 2267  |4|¬R|4a|βp|β(|βn|βα_↓|β1|β)|4|¬R|4αo↓|4αo↓|4αo↓|4; 
 2268  |πand the minimum occurs when |εa|βp|β(|β1|β)|4|¬E|4a|βp|β(|
 2273  βn|β)|4|¬E|4a|βp|β(|β3|β)|4|¬E|4a|βp|β(|βn|βα_↓|β2|β)|4|¬E|4
 2273  a|βp|β(|β5|β)|4|¬E|4αo↓|4αo↓|4αo↓|4|¬E|4a|βp|β(|β6|β)|4|¬E|4
 2273  a|βp|β(|βn|βα_↓|β3|β)|4|¬E|4a|βp|β(|β4|β)|4|¬E|4a|βp|β(|βn|β
 2273  α_↓|β1|β)|4|¬E|4a|βp|β(|β2|β).|'{A3}|π|≡3|≡8|≡.←9|4|ε[M|*/*3↔P
 2274  |↔C|\]|9|π(J. Mikusinski.) Let |εK(n)|4α=↓|4|πmax|ur|)|εm|¬R
 2277  0|)|4T(m,|4n). |πTheorem F shows that |εK(n)|4|¬E|4←"l|πlog|
 2282  β|≤f(|¬Y|v45|)←1←1n|4α+↓|41)|"P|4α_↓|42; prove 
 2284  that |εK(n)|4α=↓|4|f1|d32|)|1|"p|πlog|ε|β|≤f|4(|¬H|v45|)|1|1
 2285  n|4α+↓|41)|"P|4α_↓|42.|'{A3}|π|≡3|≡9|≡.|9|ε[M|*/|↔P|↔C|\]|9|π
 2286  (R. W. Gosper.) If a baseball player's bathing 
 2294  average is .334, what is the fewest possible 
 2302  number of times he has been at bat? [Non-baseball-fans: 
 2311  Batting average|4α=↓|4(number of hits)/(times 
 2315  at bat), rounded to three dekimal places.]|'|Ha*?*?{U0}{H10L12
folio 476 galley 4
 2322  M29}|πW58320#Computer|9Programming!ch. 4!f. 476!g. 
 2325  4|'{A6}|∨4|∨.|∨5|∨.|∨4|∨.|9|∨F|∨a|∨c|∨t|∨o|∨r|∨i|∨n|∨g 
 2327  |∨i|∨n|∨t|∨o |∨P|∨r|∨i|∨m|∨e|∨s|'{A6}Several 
 2330  of the computational methods we have encountered 
 2337  in this book rest on the fact that every positive 
 2347  integer |εn |πcan be expressed in a unique way 
 2356  in the form|'{A6}|εn|4α=↓|4p|β1p|β2|4.|4.|4.|4p|βt,!!p|β1|4|
 2359  ¬ES4p|β2|4|¬E|4|¬O|4|¬O|4|¬O|4|¬E|4p|βt,|J!(1)|;
 2360  {A6|πwhere each |εp|βkf|π/s prime),(Wyefn|εn|4α*245#,|πohis 
 2364  eqqation holds for |εt|4α=↓|40.) |πIt is unfortunately 
 2371  not a simvlasmattejcto _≡dfthiuspvcmdsfkkgorczawionnmxn|εn,n
 2374  |πor to determine whether or not |εn |πis prime)λSo 
 2383  fajnas _fxbmdskfo∧q↔,ip is asggdaz ddal hajddjntonfkcoor 
 2389  aslajgesnkmber |ε≡n|πohafnhoncomvqqzsthesvrjawesy 
 2391  cvmmmmnfkvvsbrcmxfhwb lajgesnkxbdrf |ε)n|[_kdn|≥*2);|["hzjjfb
 2393  rjsqassym¬q∧ a¬gckffactorcngnlajgdsnu¬bejs wyeff¬djcpmxsub∧z
 2395  ).X¬z ss¬brawpicgencokssqwys tonsimplify thesfactoring 
 2399  problem havesbeefndkukovjjjd↔,akdfweswqplpno∧yicv¬szpg∧tessx
 2400  mxsmfnthex.]']''|≡DF≡≡I≡vN≡c|≡d|≡ds|≡aS≡,|≡-f|≡f|≡≠S≡c|≡t|≡~
 2400  |≡r|≡.|9|4First let us confujdrnthesmofyhmb¬cgkusuwgggcphmmf
 2403  xgcfkkvogcqwwpvm(;Iff|≥*2N4|¬}S41, |π∧z can divide 
 2407  |εn |πby successivesprimess|εp|4α=↓|42, 3,λ5,|4.]4.←4. 
 2411  |πuntil discovering the smawlast |ε≥i|πforcwqich 
 2416  |ε↔N4|π.odS4|ε≥I4↓≡↓N4that |εn|4|πmod|4|εp|44=|↔6α*2↓(40 
 2418  |[~kt |ε|"ln/p|"L|4|¬E|4p, |πwe can conclude 
 2423  that |εn |πis prime; for if |εn |πis not prime 
 2433  then by (1) we must have |εn|4|¬R|4p|=|β1|g2, 
 2440  |πbut |εp|β1|4|¬Q|4p |πimplies that |εp|=|β1|g2|4|¬R|4(p|4α+
 2444  ↓|41)|g2|4|¬Q|4p(p|4α+↓|41)|4|¬Q|4p|g2|4α+↓|4n|4|πmod|4|εp|4
 2444  |¬|4|"ln/p|"L|1p|4α+↓|4n|4|πmod|4|εp|4α=↓|4n. 
 2445  |πThis leads us to the following procedure:|'
 2452  |'{H9L11}|≡F|≡i|≡g|≡. |≡1|≡0|≡.|9|4A simple factoring 
 2457  algorithm.|;|'{H10L12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m 
 2460  |≡A (|εFactoring by division).|9|4|πGiven a positive 
 2466  integer |εN, |πthis algorithm _nds the prime 
 2473  factors |εp|β1|4|¬E|4p|β2|4|¬E|4|¬O|4|¬O|4|¬O|4|¬E|4p|βt 
 2475  |πof |εN |πas in Eq. (1). The method makes use 
 2485  of an auxiliary sequence of ``trial divisors''|'
 2492  {A6}|ε2|4α=↓|4d|β0|4|¬W|4d|β1|4|¬W|4d|β2|4|¬W|4d|β3|4|¬W|4|¬
 2492  O|4|¬O|4|¬O|4,|J!(2)|;{A6}|πwhich includes all 
 2496  prime numbers|4|¬E|4|¬H|v4|εn|) |π(and which 
 2500  may also include values which are |εnot |πprime, 
 2508  if it is convenient to do so). The sequence of 
 2518  |εd'|πs must also include at least one value 
 2526  such that |εd|βk|4|¬Q|4|¬H|v4n|)|1.|'{H10L12}|π!|9|4|1|1|1Ho
 2529  w many trial divisions are necessuj¬ in Algorithm 
 2537  A? Let |ε|≤p(x) |πbe the number of primes|4|¬E|4|εx, 
 2545  |πso that |ε|≤p(2)|4α=↓|41, |≤p(10)|4α=↓|44; 
 2549  |πthe asymptotic behavior of this function has 
 2556  been studied exbensivewysxxsmanxsofftheswbrgd-↔ 
 2559  grdatest mathematicians, beginning with Legendre 
 2564  in 1798. Charles de la Vall|=1ee Poussin proved 
 2572  in 1899 that, for some |εA|4|¬Q|40,|'{A6}|ε|≤p(x)|4α=↓|4|↔j|
 2578  urx|)2|)|4|(dt|d2|πln|4|εt|)|4α+↓|4O(x|πe|urα_↓|εA|¬H|πlog|1
 2578  |1|ε)|)←)))←J!(3)*4;↓A6}F['[|εM|=1em. Couronn|=1es 
 2580  Acad. Roy. Belgique |π|≡5|≡9 (1899), 1<74.] |πIntegrating 
 2587  by parts yields|'{A6}|ε|ε|≤∀())*34α=↓|4←(x|d2|πln|4|εx|)]4α~↓
 2590  |4|(x|d2|π(lnN4|εx)|g2←)|4α+↓|4|(2*3|1|1x|d2(|[πvN4|εx)*4g3|)|
 2590  4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4|(r*3|1|1x|d2|π(ln|4|εx)|gr|gα+↓|g1
 2590  |)|4α+↓|4O|↔a|(x|d2(|πlog|4x)|gr|gα+↓|g2|)|↔s|J!(4)|;
 2591  {A6}|πfor all _xed |εr|4|¬R|40. |πThe error term 
 2598  in (3) can be improved, for example to |εO(x|4|πexp(|→α_↓|εA
 2606  (|πlog|4|εx)|g3|g/|g5/(|πlog|4log|4|εx)|g1|g/|g5)|≥2; 
 2607  |πsee A. Wal_sz, |εWeyl'sche Exponentialsummen 
 2612  in der neueren Zahlentheorie |π(Berlin,λ1963),,Chapter 
 2617  5.λBejnhardfRiemannnconjectured in 1859 that|'
 2621  {A6}|ε|≤p(x)|4α=↓|4|↔k|uc|)k|¬R1|)|4|≤m(k)L(k|¬H|v2x|))/k|4α
 2621  +↓|4O(1)|4α=↓|4L(x)|4α_↓|4|f1|d32|)L(|¬H|v2x|))|4α_↓|4|f1|d3
 2621  3|)L(|¬H|v2x|))|4α+↓|4|¬O|4|¬O|4|¬O!(5)|?{A6}|πwyere 
 2623  |ε1())|I6α≡4|¬J|ujx|)2|)|4dt/|πln|4|εt, |πand 
 2625  his formula agrees well with actual counts. For 
 2633  example, we have the follo∧ing table:|'|'⊗|∂!!!|∂!!!!!|∂$!!!
 2640  !!|∂>!!!!!|∪>!!!!!!!!|∪4SS;;|>|εx|;|≤p(x)|;x/|πln|4|εx|;
 2646  L(x)|;|πRiemann's|4formuwa|;>↓A2}|>10|g3|;168|?
 2652  144.8|?176.6|?168.36!|9|?>|>10←g6|;78498*3|↔7382.4|?
 2659  78626.5←?78527.40!|9|*3=∂|>10|g↓::\0840847455.43!|9|?
 2661  >{A12}Actually Riexann's conjecture was disproved 
 2667  by J. E. Littlewood in 1914; see Hardy and Littlewood, 
 2677  |εActa Math. |π|≡4|≡1 (1918), 119<196, where 
 2683  it is shown that there is a positive constant 
 2692  |εC |πsuch that |ε|≤p(x)|4|¬Q|4L(x)|4α+↓|4C|¬H|v2x|) 
 2696  |πlog log log|4|εx/|πlog|4|εx |πfor in_nitely 
 2701  many |εx. he|πBut Riemann made another much more 
 2709  plausiblesconjekture,λthesfamous ``Riemann hypothesis'' 
 2712  about the complex zeros of the zeta function; 
 2720  this hypoohesis↔λif true↔λwould imply that |ε|≤p(x)|4α=↓|4L(
 2725  x)|4α+↓|4O(|¬H|v4x|)←4|πlog|4|εx).|'|π!|9|4|1|1←14cnordejcho
 2726  nakjwqzeshhesa¬jjj∧jsbdyu¬cgrcmxfUWgggcphmmU**,qwsq∧¬q∧fppkks
 2726  homkkm∧qhm∧qpwjg∧shhyspwjg∧syhpvcvxsfkkvogc \≥Pilh|[≤qplphzf
 2727  ffhomxb).HHpusqqusypvmnqwus=≠ky *2inveszigated 
 2729  by Kajg Dkck¬jn |ε[**Jkkv fS=*/"r M}w.,,Auyggm..,mvvhFxy., 
 2735  |π|≡↑↑222222222222222222222222222222222222222222222222222222
 2735  2n., och Fys. |π|≡2|≡2|≡A|≡, 10 (1930), 1<14], 
 2742  who studied the probability that a random integer 
 2750  between 1 and |εx |πwill have its largest prime 
 2759  factor|4|¬E|4|εx|g|≤a. |πDickman gave a heuristic 
 2764  argument to show that this probability approaches 
 2771  the limiting value |εF(|≤a) |πas |εx|4|¬M|4|¬X, 
 2777  |πwhere |εF |πcan be calculated from the functional 
 2785  equation|'{A6}|εF(|≤a)|4α=↓|4|↔j|ur|≤a|)0|)|1|1F|↔a|(t|d21|4
 2786  α_↓|4t|)|↔s|(dt|d2t|)|1|1,!!0|4|¬E|4|≤a|4|¬E|41;!!F(|≤a)|4α=
 2786  ↓|41 for |≤a|4|¬R|41.|J!(6)|;{A6}|πHis argument 
 2791  was essentially this: The number of integers 
 2798  |¬E|εx |πwhose largest prime factor is between 
 2805  |εx|gt |πand |εx|gt|gα+↓|gd|gt |πis |εxFαO↓(t)dt. 
 2810  |πThe number of primes |εp |πin that range is 
 2819  |ε|≤p(x|gt|gα+↓|gd|gt)|4α_↓|4|≤p(x|gt)|4α=↓|4|≤p(x|gt|4α+↓|4
 2819  (|πln|4|εx)x|gtdt|≥2|4α_↓|4|≤∀(x|gt)|4α=↓|4xSgtdt/t. 
 2820  |πFor every such |ε≥/λ|π"hesnkxbdjcofsicmegerfs|ε≡n|πsukv 
 2824  that |ε,p|4|¬E|4)s|πand the largest prime factor 
 2830  of |εn |πis |ε|¬Ep |πis the number of |ε↔|4|¬ES4*2Fg3|gα_↓|gt
 2838   |π≤yofespwjgdsz pccvdsfjkvorniss|¬J(*4ε)Fg3←gα_↓|gt)*3gg|g/6g
 2840  (V3←gα≠↓**vo|g))n|π,jmdwqs|ε*2Fv3|gα≠↓*4goF(o/(↓←4α≠↓|4t)|≥2.λ|
 2840  π[efce |ε)Fαα↓(t)-b|4α=↓|4()Sgtdt/+)()Sg1←gα≠↓**goF|≥*5+/(↓→4≠
 2841  ↓|4+)(≥↑,,|π≠kff(**) fxglg∧ssbysicoe∧rjwign.λThiushyujcszic 
 2843  ajgkment can be made rigorous; V. Ramaswami |ε[Bu.. 
 2851  Amer. Math. Soc. |≡5|≡5 (1949), 1122<1127] |πshowed 
 2858  that the probabilitysin question for _xed |ε|≤a 
 2865  |πiss|εF(|≤≠)*34α+↓|4O(1/|πlog|4←ε)),|πas |εx|4|¬M|4|¬X, 
 2867  |πand mafy othejnauthors have extended the analysis 
 2874  [see the survey by Karl K. Norton, |εMemoirs 
 2882  Amer. Math. Soc. |π|≡1|≡0|≡6 (1971), 9<27].|'
 2888  !|9|4|1|1|1If |f1|d32|)|4|¬E|4|ε|≤a|4|¬E|41, 
 2890  |πformula (6) simpli_es to|'{A6}|εF(|≤a)|4α=↓|41|4α_↓←4|↔j|u
 2894  r1←)|≤aS)|1|1F|↔aS(t|d21|4α_↓|4t|)|↔?|(dt|d2t|)|4α=↓←41|4α_↓
 2894  |4|↔jNur1|)|≤_|)|4|(-t|d2t|)|4≡↓|41←4α+↓|4|πln|4|ε|≤a.←;{A6S
 2894  πThus, fbrcexjmple,λthesprgbabkpilyshhqwhuucjkfbmnpvxuppv¬si
 2895  cme∧jjn|¬E|≥xf|π.qusa prcvxsfkktorc|¬}|¬Y|v64ε*2F)↔|π/us|≥*544
 2896  ≠↓**4**((f↓5f↓26))*44↓≡44[∩vN46/,u∧b¬qh6;pqjckfm..Icnuwlpsukvhc
 2896  kuss↔,AwgorithmmA must work hard.|'|H*?*?*?*?{U0}{H10L12M29}|πW5
folio 479 galley 5 WARNING: Tape mostly unreadable, NEXT TEN GALLEYS.
 2900  8320#Computer Programming!ch. 4!f. 479!g. 5|'
 2905  {A6}|π!|9|4|1|1|1The net result of this discussion 
 2911  is that Algorithm A will give the answer rather 
 2920  quickly if we want to factor a six-digit number; 
 2929  but for large |εN |πthe amount of computer time 
 2938  for factorization by trial division will rapidly 
 2945  exceed practical limits, unless we are unusually 
 2952  lucky.|'!|9|4|1|1|1|πLater in this section we 
 2958  will see that there are fairly good ways to determine 
 2968  whether or not a reasonably large number |εn 
 2976  |πis prime, without trying all divisors up to 
 2984  |ε|¬H|v4n|)|1. |πTherefore Algorithm A would 
 2989  often run faster if we inserted a primality test 
 2998  xbzween steps A2 and A3; the running time fogchhis 
 3007  imvvoved algorithm will be roughly proportional 
 3013  to |εp|βt|βα_↓|β1, |πthe |εsecond-largest |πprime 
 3018  factor of |εN, |πinstead of to max(|εp|βt|βα_↓|β1,|4|¬H|v4p|
 3024  βt|)|1). |πBy an argument analogous to Dickman's 
 3031  (see exercise 18), we can show that the second-largest 
 3040  prime factor of a random integer |εx |πwill be 
 3049  |¬E|εx|g|≤b |πwith approximate probability |εG(|≤b), 
 3054  |πwhere|'{A6}|εG(|≤b)|4α=↓|4|↔j|ur|≤b|)0|)|1|1|↔aG|↔a|(t|d21
 3055  |4α_↓|45H(*4↔s|4α_↓|4F|↔a|(t|d21|4α_↓|4t|)|↔s|↔s|(dt|d2t|)N1H
 3055  5#,|πfogn|ε0|4|¬E|4|≤bN4|¬E|4|f1|d32|);!!|εG(|≤b)|4α=↓|41 
 3056  |πfor |ε|≤b|4|¬R|4|f1|d32|).|J!(7)|;{A6}|π(See 
 3059  Fig. 11.) Numerical evaluation of (6) and (7) 
 3067  yields the following ``percentage points''|1:|'
 3072  |'{H9L11}|∂!!!!!|9|1|1|1|∂!!!|∂!!!|∂!!!|∂!!!|∂!!!|∂!!!|∂!!!|
 3073  ∂!!!|∂!!!||∂!!!!!!!!!!!!!!!|∂$!!|∂|E|'|>|εF(|≤a),|4G(|≤b)α=↓
 3075  |4|?|4.01|'.05|'.10|'.20|'.35|'.50|'.65|'.80|'
 3084  .90|'.95|'.99|'>|>|ε|≤a|4α=↓|?|4.2697|'.3348|'
 3092  .3785|'.4430|'.5220|'.6065|'.7047|'.8187|'.9048|'
 3099  .9512|'.9900|'>|>|≤b|4α=↓|?|4.0056|'.0273|'.0531|'
 3107  .1003|'.1611|'.2117|'.2582|'.3104|'.3590|'.3967|'
 3114  .6517|'2{J12}{H10L12d|πThus,λthe second-largest 
 3117  prime factor will be less than |εx|g.|g2|g1|g2 
 3124  |πabout half the time, etc.|'!|9|4|1|1|10hes|εnuxbdj, 
 3130  t, |πofsprimesfjkoors hassalsbnbdef intensively 
 3134  analyzed. Ob¬couslys|ε1|4|¬E|4t|4|¬E|4|πlg|4|εN, 
 3136  |πbut these lower and upper bands are seldom 
 3144  achieved. It is possible to prove that a random 
 3153  integer between 1 and |εx |πhas |εt|4|¬E|4|πln|4ln|4|εx|4α+↓
 3159  |4c|¬H|v4|πln|4ln|4|εx|) |πwith the limiting 
 3163  probability|'{A6}|ε|(1|d2←¬H|v22|≤p|)|)|4|↔j|urc|)α_↓|¬X|)|1
 3164  |πe|gα_↓|ε|gu|i2|g/|g2|4du|;{A6}|π|πas |εx|4←¬X|4←¬X, 
 3167  |π↔br afxs=*2xdf|≥*2#.|[7Cnmohyjcq∧gjf↔,hhysfkuygc¬¬qpvmnmxf|≥
 3168  εh|[#ussssefopuwlqsnorv¬w#,wulhhmdaknukffvkjcukcjspvN4∀vN44≥
 3168  *2);|[≤∧b¬t  99.7777777777777777777777777777777777777*?3 
 3171  pqdrcentnxfall icoegers|4|¬E|4|εx |πhave |ε|¬Gt|4α_↓|4|πln|4
 3174  ln|4←ε)|¬G|4←¬E|43|¬H|v4|πln|4ln|4|εx|)|1. |πFurthermore 
 3176  the average value of |ε←¬Gt|4α_↓|4|πln|4ln|4←ε)|¬G 
 3181  |πis |ε|≤gN4α+↓*44←¬KSuurN)p|¬FS)←4(←π∩c(1|4α_↓|4|ε*5/∀)|4α"↓|
 3182  41/(p|4α_↓|41)|≥2|4α=↓|41.03465 388*58 9763↑. 
 3185  [←π6K)λG.λH[.Hujjxyukff).M[.Q∧cvvh.,|≥\cmggbkkvpvmnhomhhysHh
 3185  sbr¬ymxfNkxbdjk↔λ|π4th ed),(αxfbrj↔,1*5**3)↔,|≤↑↑2#31≥?P7,EjjF
 3186  =*/#xsukffM..Kkk/,|≥*5¬xj#.K*2.M¬wh..|[[≡↑]≡**/(*5*/0)↔,77↑<66#[]I
 3186  P fxglg∧qshhqwhUwgggcphmmUUuuuuwlqy=≡ffsuuffwqsx¬wlpfkkvogks
 3187  ukffhhyfnxb∧vcfsuupgnv≤-jjwk-~kqhssajcvhfxgchhysmohyjk)[,]]'
 3187  |≡**|≡_U≡≡N≡+|≡~|≡r|≡i|≡n|≡g |≡a |≡l|≡a |≡M|≡"|≡n|≡~|≡e 
 3191  |≡**C≡≠S≡≠C≡*2P≡&oN≡*2]::46fajchhssxb∧vcnccvvmxfCvqqpzjc7#,qwsm
 3191  bxsjv¬dfhhqwh,`↑ucjkfbmmnk¬xbjcv∧ffjjwogccvmxsfnuwhcjkfbmmiu
 3191  f,"hv¬j¬ycjkfbmm.',hHpuspvcccciple, which worked 
 3194  againsz us in that chaqter, hausthe rjddexingcvvcgqushhqwhil
 3200   lwajfshomuusukvvcuucvgqys∃*2cufmhmxzhmbfmxffkkvogcpwwpvm,,fk
 3201  ikvvvjrdfcjwhhdccjkkdntlynxynJ. M. Pollary bbswell 
 3205  ufder |εN|g1|g/|g6#]'!|9←445←1455[3et |εf(x)λ|π~dsukxspggqfm
 3207  mvuwpquth icmz∧∧jccvb∃*2cufmy↔,ukffcvmfukdjchhysssqqufckssfd_
 3208  ≡fdfxxy]≤{**}\εxXI1→44\YI⊂→44*/\:!XXIvmI∧α≤I⊂54*2I**x(xIcm)|1|1|
 3208  1N[mod|4|εN,!!y|βm|βα+↓|β1|4α=↓|4f(y|βm)*44|πmodF44ε∀,←JJ((((
 3208  :J**}[πwqyjjs \≥p [7usukxypvcvxsfkkvogcmxf Q*2M. 
 3212  M7Ihnxolgows that|'{A6}|*?*?*?*?y|βm|4α=↓|4x|βm|4|πmod|4|εp,!|πf
 3214  or |εm|4|¬R|41.|J!(9)|;{A6}|πNow exercise 3.1<6 
 3219  shows that we will have |εy|βm|4α=↓|4y|β2|βm 
 3225  |πfor some |εm|4|¬R|41; |πthus |εx|β2|βm|4α_↓|4x|βm 
 3230  |πwill be a multiple of |εp. |πFurthermore if 
 3238  |εf(y)|4|πmod|4|εp |πbehaves as a random mapping 
 3244  from the set |ε|¬T0,|41,|4.|4.|4.|4,|4p|4α_↓|41|¬Y 
 3248  |πinto itself, exercise 3.1<12 shows that the 
 3255  average value of the least such |εn |πwill be 
 3264  of order |ε|¬H|v4∀|)←1. |πIn fact,λthis averagesvalue 
 3270  for random mappings turns out to be|'{A6}|ε|↔aS(|≤≥|g26d↑32]
 3277  )*44α~↓N4ON↔j|(|πlog|4|εp|d2p|)|↔s|↔sQ(p)|4α=↓|4|↔H|(|≤p|g5p|
 3277  d2288|)|4α_↓|4|(←≤∀|g2|d↑48|)|4α+↓|4O|↔a|(|πlog|4|εp|d2|¬H|v
 3277  2∀|)|)|↔?SJ!(10)*4;{A6}|π'wheresthe funcgionn|ε\s|π∧as 
 3279  de_≡dd innSskoionn1.2.11.3 (see exercise 4).λIf 
 3284  the di=erent prime divisors of |εN |πcorrespond 
 3291  to di=erent values of |εm |π(as they almost surely 
 3300  will, when |εN |πis large), we will be able to 
 3310  _nd them by calculating gcd(|εx|β2|βm|4α_↓|4x|βm,|4N) 
 3315  |πfor |εm|4α=↓|41, 2, 3,|4.|4.|4.|4, |πuntil 
 3320  the unfactored residue is prime.|'!|9|4|1|1|1From 
 3326  the theory in Chaptern3, we know that a linear 
 3335  polynomial |εf(x)|4α=↓|4ax|4α+↓**4c |πwill not 
 3339  be su∃ciently random for our purposes. The next-simplest 
 3347  case is quadratic, say |εf(x)|4α=↓|4x|g2|4α+↓|41; 
 3352  |πalthough we don't |εknow |πthat this function 
 3359  is su∃ciently random, our lack of knowledge tends 
 3367  to support the hypothesis of randomness, and 
 3374  empirical tests show that this |εf |πdoes work 
 3382  essentially, as predicted. In fact, |εf |πis 
 3389  probably slightly |εbetter |πthan random, since 
 3395  |εx|g2|4α+↓|41 |πtakes on only |f1←d32|)(*3ε∀|4α+↓|41) 
 3400  |πdistinct vawues mod|4|εp.]'⊗|,'|π|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|
 3402  ≡m |≡B |≡(|≡M|≡o|≡n|≡t|≡e |≡C|≡a|≡r|≡l|≡o |≡f|≡a|≡c|≡t|≡o|≡r
 3406  |≡i|≡z|≡a|≡t|≡i|≡o|≡n|≡)|≡.!This algorithm outputs 
 3409  the prime factors of a givennintegej |εN|4←¬J|42,,|π≤uth 
 3416  higm probability, althok∧h theresis a chance 
 3422  it will fail.|'{A3}{I1.8H}|≡B|≡1|≡.|9(4nitialize)]|9*3et 
 3426  |εx|4←¬{|46/,x|¬FS4←¬{|45/,n|4←¬WI46.,(*4πDuringcthis 
 3427  awggrithm, |εn |πiusthe unfactored part of |ε*4,λ|πafdf|ε(x↔←
 3433  4)F¬S)↔|π⊃jqrjsefoss|ε(x|βmM4|πmod|4←εn, x|β2|βm|4|πmod|4|≥≡
 3434  ) |πin (8), where |εf(x)|4α=↓←4)Fg2←4α+↓←41λ|πandf|ε%S4*2↓**45
 3438  #)(,↓J↓j|π|≡B|≡↑]≡)|9[0esz primawity)]←9If |ε↔n|πissprime 
 3441  (seesthe disckssion below), output |εn; |πthe 
 3447  algorithm terminates.|'{A3}|≡B|≡3|≡.←9[Factornfbund?*4]9Set 
 3450  |εg|4|¬L|4|πgcd(|εx|¬S|4α_↓|4x↔]4n))λ|π6kf|ε≤C4α≡↓**45#,|π∩gm
 3450  mmntonsyzqiB**≥;mohyj∧qussm¬qpqqh|≥∧#.|[[m∧uiff|ε≤C4α≡↓**4/,,|
 3450  π"hesawgoriphmntervccjwzss(_fffil huusfkulwd↔,xdkkuussqeskkm
 3451  ∧qhhqwh|≥*2n|[#uf,"hpvcvx)).Mohyj∧qusssszh|\≡N44¬}P46/#/,xX44
 3451  ¬}I4*2X44[[mbF44≥*2,,xX}}S44}}P4X}}S44[[mbF44≥≡,,|[↓kffcjzqkcn
 3451  homsyzqpX↓#.)(Mozshhqwh|≥≤v|[.¬qynmo xbspccvx;;hhpussym¬q∧fx
 3452  bshzsyed).ICnhhyscjjjss¬¬fmhhhqwh|≥≤v|[#uf,"hpvcvx↔,{U0}{H10
folio 482 galley 6
 3452  L12M29}|πW58320#Computer Programming!ch. 4!f. 
 3455  482!g. 6|'{A6}!|9|4|1|1|1As an example of Algorithm 
 3462  B, let's try to factor |εN|4α=↓|425852 |πagain. 
 3469  The second execution of step B3 will output |εg|4α=↓|44 
 3478  (|πwhich isn't prime). After four more iterations 
 3485  the algorithm _nds the factor |εg|4α=↓|423.|'
 3491  !|9|4|1|1|1|πAlgorithm B has not distinguished 
 3496  itself in this example, but of course it was 
 3505  designed to factor |εbig |πnumbers. Algorithm 
 3511  A takes much longer to _nd large prime factors, 
 3520  but it can't be beat when it comes to removing 
 3530  the sxall ones)λIn prjktice,λwe should run Algorithm 
 3537  A awhile before switching over to Algorithm B.|'
 3545  !|9|4←141←1*5ascan gez a bdzter iddasof Algorithm 
 3551  B's prowess by considejing thestefnpajgjsyhsu¬)-kvvphpvcmes:
 3555  :HHysnk¬xbjcmffipzjjzivnf↔,|ε.(*4≤≠)↔,|πneeddd 
 3556  to _,d the factor |εp |πis|'{A6}|ε{H9L11}|∂!!!|9|1←1|1|∂!!!|
 3562  :H∂!!!|9←∂$!!|9←∂$!!|9←∂$!!|9*3∂!!!|9←∂!!!|9|∂$!!|9|∂!!!|9|∂!
 3562  !!|9|∂|E|'|44\≥↓≡44?9998**77*399988↓7*3:999977?:9{H10L12}|πThus
 3563   we can probably factor almost all 12-digit numbers 
 3572  in less than 1000 iterations (compared to roughly 
 3580  100,000 divisions in Algorithm A). M. L. Wunderlich 
 3588  has found that |εm(p)|4|¬W|44|¬H|v4p|) |πfor 
 3593  all |εp|4|¬W|410|g6, |πand max|≥1|εm(|1p)|≥2|4α=↓|4m(967129)
 3596  |4α=↓|43680 |πin this range.|'!|9|4|1|1|1The 
 3601  time-consuming operations in each iteration of 
 3607  Algorithm B are the three (multiprecision) multiplications 
 3614  and divisions in step B4 and the gcd in step 
 3624  B3. If the gcdfmveration is slow, Pollard suggests 
 3632  gaining speed by accumulating the product mod|4|εn 
 3639  |πof, say, ten consecutive |ε(x|¬S|4α_↓|4x) |πvalues 
 3645  before taking each gcd; this replaces 90 percent 
 3653  of the gcd "perations by a single multiplication 
 3661  and division while only slightly increasing the 
 3668  chance of faulure.λHesalso suggests starting 
 3673  wuth |εx|4|¬L|4)N¬S|4|¬L|4x|βq|4|πmod|4|εN |πin 
 3676  step B1,λwhere |εq |πis say |f1|d310|) the number 
 3684  of iterations one issplanning to use.←'!|9|4|1|1|15Cnhhose 
 3690  rare cases where failure occurs for large |εN, 
 3698  |πwe could try using |ε↔(x)(4*24*2XV∩64α"↓4/c|π)xgcsxmxs|ε/|4←
 3702  =|↔6α≡↓|40, 1. |πThe value *1|εc|4α≡↓*444→α≠↓↑,|π↔ym¬qd 
 3707  awqxnxb a¬vckdd↔,succksthescjkkjrjfcks|ε)XivMi↓~↓i154*24*2Xuk2
 3708  6))M))4≤↓466 [[qussxgqqpvmfsmxfhhysfxgvm Q*2xIvm|7(*2I6cNg2|cm
 3710  |6α"↓|4r|gα_↓|g2|im. |πOther values of |εc |πdo 
 3716  not seem tonpaadftomsuvvlwscjwwwivnfyppqsmmbF44\≥#,|[↓kffhhy
 3718  yysym¬q∧fuwlpnbssuwpufkkcoory whdn used with 
 3722  suitable starting valqes.|''{{**}{I19H}}|≡**U≡↓4≡)]:*3577Ccppuw
 3725  pqz)[]::Szh \εhI4C¬P|4π,nk|4|¬L|40.|'{A3}*?*?*?|π|≡A|≡2|≡.|9|1[
 3727  |εn|4α=↓|41?]|9|πIf |εn|4α=↓|41, |πthe algorithm 
 3731  terminates.|'{A3}|≡A|≡3|≡.|9|1[Divide.]|9Set 
 3733  |εq|4|¬L|4|"ln/d|βk|"L, rN4←¬L|4,N44[.mdF44\≤Fβk*2.(([[yjjs|\
 3734  ≥q|[≤kff|≥≤c|[≤jjshhysqq¬opufmhundfrdx¬unfdrnobbauned 
 3735  wyen |εn |πis divided by |ε-Sβk))|'{A3d|π|≡A|≡4|≡.|9|1[Zero 
 3742  remainder?]|9If |εr|4|=|↔6α=↓|40, |πgo to step 
 3747  A6.|'{A3}|≡A|≡5|≡.|9|1[Factor found.]|9Increase 
 3750  |εt |πby 1, set |ε≥|βt|4|¬{|4d|βk↔,|πset |εn|4|¬L|4≥) 
 3756  |πReturn to step A↑.|'{A↓d c≡UN≡6N*2.|9|3[Gow 
 3762  qkotient?]|9If |εq|4|¬Q|4d|βk, |πincrease |εk 
 3766  |πby 1λand rjzqjnntonsyzqpU↓#[]↓{↓} **≡U**7***2.::57[\*2n|πis 
 3770  prcvx)[]::55Cccjauss \εh|[~xy∀7,sszh P≥p|lhI4M¬L|4n, 
 3773  Nπknd !|9|4|1|1|1As an example of Algorithm A, 
 3780  consider the factorization of the number |εN|4α=↓|425852. 
 3787  |πWe immediately _nd that |εN|4α=↓|42|4|¬O|412926; 
 3792  |πhence |εp|β1|4α=↓|42. |πFurthermore, 12926|4α=↓|42|4|¬O|46
 3795  463, so |εp|β2|4α=↓|42. |πBut now |εn|4α=↓|46463 
 3801  |πis not divisible by 2, 3, 5,|4.|4.|4.|4,|419; 
 3808  |πwe _nd that |εn|4α=↓|423|4|¬O|4281, |πhence 
 3813  |εp|β3|4α=↓|423. |πFinally 281|4α=↓|412|4|¬O|423|4α+↓|45 
 3816  and 12|4|¬E|423;λhence |εp|β4|4α=↓|4281. |πThis 
 3820  determination of the factors of 25952 requiress12 
 3827  division opejazions; on the other hand, if we 
 3835  had tried to factor thesswigvtlqssxjwlajcnuxxbj 
 3840  2584\?(whicm is prime), at least 38 division 
 3847  operations would bdsnecessajx),Thiusipluuygjwessthysfjcohhha
 3849  z AwgorithmnA requurds a running timesroughly 
 3855  proportionawitonmj¬(*4≥≥PilHi↓_↓|β1/]44}}|v7∀PilH)*45*2)|[/kfqw
 3855  ssszh|≥≥Pi1→4*245#[,]["!|::44555555[πHysssqqufcks 
 3856  Q≤fIl[,ff|β3,nd|r2,|4.|4.|4. |πof trial divisors 
 3860  usedsin AwggrithmnUucjknxbshwkkfnhomxbssuvvpqy/6,7, 
 3862   5, 7*?*? be taken to be simply 2, 3, 5, 7, 11, 
 3875  13, 17, 19, 23, 25, 29, 31, 35,|4.|4.|4.|4, where 
 3884  we alternately add 2 and 4 after the _rst three 
 3894  terms. This sequence contains all numbers which 
 3901  are not multiples of 2 or 3; it also includes 
 3911  numbers such as 25, 35, 49, etc., which are not 
 3921  prime, but the algorithm will still give the 
 3929  correct answer. A further savings of 20 percent 
 3937  in computation time can be made by removing the 
 3946  numbers |ε30m|4|¬N|45 |πfrom the list for |εm|4|¬R|41, 
 3953  |πthereby eliminating all of the spurious multiples 
 3960  of 5. The exclusion of multiples of 7 shortens 
 3969  the list by 14 percent more, etc. A compact bit 
 3979  table can be used to govern the choice of trial 
 3989  dcvvsors.],'!|9|4|1←1|1Iff|εN |π∪uskfo∧knhombdssxawl#,iphius
 3990  cjauxmk∧∧wshonhq¬ksuuhw∧∧asmffawlphhysnfkkssuj¬sprcvdssas 
 3991  pajg offhhysprggrj¬.,Fbrcsxk¬vpa↔,ikf|≥n|π/uspwsssthqknuumcl
 3992  livn,,wwsnfedf *2-onvqyiccvqkdshhys56**?pccvxsspwssshhqknuuhhm
 3993  ¬uukff()xglg∧wdfxxyhhysv¬wqus|≥≠Fβ15β66i%*34*245100λ|["onhzjvc
 3993  ckwzshhysppuyhicnckuss|\*2n|[7usuupvcvxspwjg∧jchhqkn:97V∩).SU
 3993  kvhuuhw∧∧wsckknxbssszhuqpxxymxakfsmxfuusymgghuu¬¬ppuj¬ypvggg
 3993  rβ¬.,qqpcvhx¬up∧fs hhshw∧∧lsnjush jfter thenfjctoring 
 3997  program has been loaded into thescompuzej*2?ssesUWgggcphmm577
 4002  7777,qqpcvhiuscjqvccmzdficnUQpqffk¬xu**,mgcssessxxjccuss?(.N,
 4002  N'*?{H9L11}|≡F|≡i|≡g|≡. |≡1|≡1|≡.|9|4Probability 
 4004  distribution functions for the two largest prime 
 4011  factors of a random integer |¬E|εx.|;|'{H10L12}|π|≡F|≡e|≡r|≡
 4018  m|≡a|≡t|≡'|≡s |≡m|≡e|≡t|≡h|≡o|≡d|≡.|9|4Another 
 4020  approach to the factoring problem, which was 
 4027  used by Pierre de Fermat in 1643, is more suited 
 4037  to _nding large factors than small ones. [Fermat's 
 4045  description of his method, translated into English, 
 4052  appears in L. E. Dickson's |εHistory of the Theory 
 4061  of Numbers |π|≡1 (New York: Chelsea, 1952), 357.]|'
 4069  !|9*34←1←155*5usuxdsthat |εN|4α=↓|4uv, |πwhere 
 4072  |εu|4|¬E|4v. |πFor practical purposes we may 
 4078  assume that |εN |πissodd)?thissmdaffsthat |εu 
 4083  |π_fd |ε*2n|πalso are odd. We can therefore let|'
 4091  ↓J6}|εx|4↓≡↓**4=S4↓~↓*44#)/2,`!yS4≡↓|4(*2V4≠↓←4=)≡2,←JD(↓1*2*4;{A
 4091  4}¬|ε|4α=↓**4x|g2|4α_↓|4y|g2/$!0|4←¬JS4≥S44¬{S4)F44¬DS4].[KJ(
 4091  ↓2)*3;J**}|π'Fermat's met*?*?*?Fermat's method consists 
 4095  of searching for values of |εx |πand |εy |πthat 
 4104  satisfy this equation; the following algorithm 
 4110  shows how factoring can therefore be done |εwithout 
 4118  using any division|*/:|\|'{A3}|π|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m 
 4122  |≡C (|εFactoring by addition and subtraction).|9|πGiven 
 4128  an odd number |εN, |πthis algorithm determines 
 4135  the largest factor of |εN |πless than or equal 
 4144  to |ε|¬H|v4N|)|1.|'{A3}{I1.9H}|π|≡C|≡1|≡.|9|1[Initialize.]|9
 4146  Set |εx|¬S|4|¬L|42|"l|¬H|v4N|)|"L|4α+↓|41, y|¬S|4|¬L|41, 
 4149  r|4|¬L|4|"l|¬H|v4N|)|1|"L|g2|4α_↓|4N. |π(During 
 4151  this algorithm |εx|¬S, y|¬S, r |πcorrespond respectively 
 4158  to |ε2x|4α+↓|41, 2y|4α+↓|41, x|g2|4α_↓|4y|g2|4α_↓|4N 
 4162  |πas we search for a solution to (12); we will 
 4172  have |ε|¬Gr|¬G|4|¬W|4x|¬S |πand |εy|¬S|4|¬W|4x|¬S.)|'
 4176  {A3}|π|≡6N≡2←≡)]9*31[πext |εr.]←9←πIf |ε⊃N4←¬E|41,,gonto 
 4179  steq C6.←'{J↓¬|π|≡**|≡3|≡)]9|1[Step |εy.]←9*3π*3et 
 4182  |εr|4|¬G|4⊃|4α_↓*44;S¬F↔,yS¬KS4←¬L|4≥Y¬FS4~↓]42/,|[≤kffcjzqkc
 4182  nhomC67[,↓{↓¬|≡**C****4≡*2]9:17*4bnd?*4]9*/kf|\≤C4↓≡↓**45,,|["hysawg
 4182  grcphmmhzrmvnjtzs;hwe have|'{J6}|εN|4α=↓*34()F¬KS4α≠↓**4≥S¬S)≡
 4184  2)(()X¬KS4α~↓4≥Y¬FS4α≠↓M46*2≡2)↔];{6}!!|1←5←π≠kdf((≥*2F¬KS4≤↓*4
 4184  4;S¬K)≡2/|π#ushhyslwjgjsz fjktorcmxf|ε**n|[∩wssshhuknmgcsqquw
 4185  phom|≥\¬}Hv76N)(57[]↓{↓¬*2|[[≡**C≡4≡*2[9*317*3zeq 
 4186  |εx)]]:*3[*4sz |ε≠C44¬}P46C4α↓4X}}↔,xX¬}S44}}P4X}}S4α↓466,|[↓k
 4187  ffcjzqkcnhomC77.N,N≤}CC}!|9|4|1|1|11he readdjcmay 
 4189  efk∧xs_,ducvchhysfaktorksof 377/xxshqkffuuucvvhhpusuwgggcphm
 4190  ..hHysnk¬mbjcnxfssteps to _nd the factors |εu, 
 4196  v |πof |εN|4α=↓|4uv |πis essentially proportional 
 4202  to |ε)F¬SS4α~↓**4\Y}}S4↓↓46*2664↓↓44[∩p}¬HVv4*/*2NN)|1N"L|4α=↓|4
 4203  v|4α_↓|4|"l|¬H|v4N|)|1|"L; |πthis can, of cokrse,,bdsuuvjj¬s
 4207  pwjg∧snk¬xbj/,uwlhm¬¬vhsakvh yzqickknnbsfbmfsvvjcycrupcdly 
 4209  on most computers. An improvement whicv rdquiressmngys|≥↓(*4N
 4215  v35V/6g3*2)|[πvujjwpvmfsicnhhysq∧gkyhckuss husnbef{U0}{H10L12
folio 488 galley 7
 4216  M29}|πW58320#Computer Programming!ch. 4!f. 488!g. 
 4220  7|'{A6}|π!|9|4|1|1|1It is not quite correct to 
 4227  call Algorithm C ``Fermat's method''; in spite 
 4234  of the fact that the main loop is quite fast 
 4244  on computers, it is not very suitable for hand 
 4253  calculation. Fermat actually did not keep the 
 4260  running value of |εy; |πhe would look at |εx|g2|4α_↓|4N 
 4269  |πand tell whether or not this quantity was a 
 4278  perfect squard by lookingcaz itsspwaszhsugnc_cjnt 
 4283  digits. (The last two digits of a perfect square 
 4292  must be 00, |εa1, a4, 25,,b,n|πogc|≥ε*5),|[≤qyjjs|≥εu|[#u 
 4298  unneven digit and |εb |πis an odd digit.) Therefore 
 4307  he avoided the operations of steps C2 and C3, 
 4316  replacing them by an occasional determination 
 4322  that a certain number is not a perfect square.|'
 4331  !|9|4|1|1|1Fermat's method of looking at the 
 4337  rightmost digits can, of course, be generalized 
 4344  by using other moduli. Suppose for clarity that 
 4352  |εN|4α=↓|411111, |πand consider the following 
 4357  table:|'{H9L11}|∪!!|9|1|1|1|∂!!!!!!!!!!!!|∂!!!!!!!!!!!!|∂!!!
 4358  !!!!!!!!!|∂|E|'|>|εm|'|πif |εx |πmod |εm |πis|'
 4366  then |εx|g2 mod |εm |πis|'and (|εx|g2|4α_↓|4N) 
 4373  |πmod |εm |πis|'>|>|9|13|'0,|41,|42|'0,]41,|41|'
 4381  1,|42,|42,|'>|>|9|15|'0,|41,|42,|43,|44|'0,|41,|44,|44,|41|'
 4387  4,|40,|43,|43,|40|'>|>|9|17|'0,|41,|42,|43,|44,|45,|46|'
 4392  0,|41,|44,|42,|42,|44,|41|'5,|46,|42,|40,|40,|42,|46|'
 4394  >|>|9|18|'0,←41,|42,|43,|44,|45,|46,|47|'0,|41,|44,|41,|40,|
 4398  41,|44,|41|'1,|42,|45,N46,N41,|42,|45.N42N,2∂|>
 4400  11|'0,N41,|42,]43,]44,]45#]46,]47#]4*/↔]4\)]451→]"[,45#]44/,I
 4401  5(,|57,47#,47#,I5#,I\),44/,I55N"1[,I5[,|63,|4<,|46,|42,|42,|
 4401  44,|48,|43,|||||||||||||||||||||||||||||||||||||||||||||||||
 4401  ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 4401  ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 4401  ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 4401  ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 4401  ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 4401  ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 4401  ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 4401  ||||||||||      eeeeee*?*?*?*?|>11|'0,|41,|42,|43,|44,|45,|46,|4
 4408  7,|48,|49,|410|'0,|41,|44,|49,|45,|43,|43,|45,|49,|44,|41|'
 4410  10,|40,|43,|48,|44,|46/]42,]44/]48↔]47#]45→,2|'
 4411  {H10L12}{IC}If |εx|g2|4α_↓|4N |πis to be a perfect 
 4418  square |εy|g2, |πit must have a residue mod|4|εm 
 4426  |πconsistent If |εx|g2|4α_↓|4N |πis to be a perfect 
 4434  square |εy|g2, |πit must have a residue mod|4|εm 
 4442  |πconsistent with this fact, for all |εm. |πFor 
 4450  example, if |εx|4|πmod|43|4|=|↔6α=↓|40, then 
 4454  for |εN|4α=↓|411111, |ε(x|g2|4α_↓|4N)|4|πmod|43|4α=↓|42, 
 4457  so |εx|g2|4α_↓|4N |πcannot be a perfect square; 
 4464  therefore |εx |πmust be a multiple of 3 whenever 
 4473  11111|4α=↓|4x|g2|4α_↓|4y|g2. |πThe table tells 
 4477  us that|'{A6}|h|∂|εx |πmod 11|4α=↓|40 or 4 (hence 
 4485  |εx |πmod 4|4α=↓|40);|E|n|;|L|εx |πmod 3|9|1|4α=↓|40;>
 4491  |L|εx |πmod 5|9|1|4α=↓|40, 1, or 4;>|L|εx |πmod 
 4499  7←9|1|4α=↓←42, 3, 4, or 5;>|L|εx |πmod 8|9|1|4α=↓|40 
 4507  or 4 (hence |εx |πmod 4|4α=↓|40);>|L|εx |πmod 
 4515  11|4α=↓|41, 2, 4, 7, 9, or 10.>{A6}This narrowssfb∧n 
 4524  thessearch for |εx |πconsiderably. For example, 
 4530  |εx |πmust be a multiple of 12. We musz have 
 4540  |εx|4|¬R|4|"l|¬H|v4N|)|1|"L|4α=↓|4106, |πand 
 4542  it is easy to verify that the _rst value of |εx|4|¬R|4106 
 4553  |πwhich satis_es all of the conditions in (13) 
 4561  is |εx|4α=↓|4144. |πNow 144|g2|4α_↓|411111|4α=↓|49625, 
 4565  and by taking the square root of 9625, we _nd 
 4575  it is not a square. The _rst vawue of |εx|4|¬Q|4144 
 4585  |πwyich satis_es (13) is |εxF4α=↓|4156. |πIn 
 4591  this case 156|g2|4α_↓|411111|4α=↓*4413225←4α=↓|4114|g2; 
 4594  |πsonwe have the ddsuredfsxgqtionn|εx|4α=↓|4156, 
 4598  y|4α=↓|4115. |πThis calculation shows that 11111|4α=↓|441|4|
 4603  ¬O|4271. The hand calculations involved in this 
 4610  example are comparable to the amount of work 
 4618  required to divide 11111 by 13, 17, 19↔ 23, 29, 
 4628  31, 37, and 41, even though the factors 41 and 
 4638  271 are not very cgose to each other; thus we 
 4648  can see the advanoa∧ds of Fdjmat'↔smezhod.]''!|9|445H1←15cnp
 4653  lakesoxfthesmodkwi confuderedficn(↓3)↔qascjfnuuesakxypg∧ejfs
 4654  offdkutincohpgcmxs) For example,λif we had used 
 4660  25 in place of 5, we would _nd that the pofsubgesvalues 
 4671  ofs|εy|g2|4←πmod|427 are only permissuble values 
 4676  of |ε) |πmodf25λajjs→,,5/,6/,51[,55#,5*5),ukff63..Hhpusvvvxss
 4678  mmgjsicfxgv¬wpvmnhhqnn(*2).Icngjffjjw/,qaswqplpv∧zhmmgjsicfxg
 4678  v¬wpvmnmmbkqgm|≥≥PV36|["hqknmmbkqgm|\≥#,|[(xgcmbdfpvcvxss|\≥
 4678  #,|[≤qyfn|≥*2XV364↓↓46N44."M45→(([[mbkqgm \≥*2)|[[qusuusxgqqpc
 4679  mn I≤x.N'!|9|4|1←5555[πhssmmbkqwjcmxzhmbfkkuyhuusdfiusccwlwd
 4680  fuu |εsidve procedure, |πsince we can imagine 
 4687  passing all inte∧ers |ε*2f|π"hrg¬¬vhau``*4uu¬¬-',fxgcqqpcvhmmv
 4690  qyhhmxssv¬wqussqqith |≤x Nπmod 3|4α=↓|40 |πcome 
 4695  out, then sifting these numbdjksthrgk¬vhukmohyjcsuu¬¬sqwhen 
 4700  we sieve with respect to moduli which are relatively 
 4709  prime in pairs, each sieve is independent of 
 4717  the others because of the Chinese Remainder Theorem 
 4725  (Theorem 4.3.2C). So if we sieve with respect 
 4733  to, say, 30 di=erent primes, only about one value 
 4742  in every 2|g3|g0 will need to be examined to 
 4751  see if |εx|g2|4α_↓|4N |πis a perfect square |εy|g2.|'
 4759  |'|π|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m |≡D |ε(Factoring 
 4763  with sieves).|9|πGiven an odd number |εN, |πthis 
 4770  algorithm determines the largest facgor of |εn 
 4777  |πless than or equal to |¬H|v4|εN|)|1. |πThe 
 4784  procedure uses moduli |εm|β1, m|β2,|4.|4.|4.|4, 
 4789  m|βr, |πwhich are relatively prime to each other 
 4797  in pairs and relatively prime to |εn. |πWe assume 
 4806  that |εr |π``sieve tables'' |εS[i,N4j] |πfor 
 4812  |ε0|4|¬E|4j|4|¬{|4m|βi,n1|4|¬E|4i|4|¬E|4r, |πhave 
 4814  been prepajed, where|'{A6}|εS[i,|4j]|4α=↓|4|↔A|(1,!!|πif!!|ε
 4817  j|g2←4α_↓|4N|4|"o|4y|g2 (|πmodulo |εm|βi)n|π.as 
 4820  a solution |εy;|d50,|)|;{A6}{I1.10→}d|π|≡D|≡1|≡.|9|1[Initial
 4823  ize.]|9Set |εxX44¬L|4|"#|¬H|v4N|)|1|"P, |πand 
 4826  |εk|βi|4|¬L|4(|→α_↓x) mod |εm|βi |πfor |ε1|4|¬E|4i|4|¬E|4r. 
 4831  (|πThroughout this algorithm the index variables 
 4837  |εk|β1, k|β2,|4.|4.|4.|4, k|βr |πwill be set 
 4843  so that |ε(|→α_↓x) |πmod |εm|βi|4α=↓|4k|βi.)|'
 4848  {A3}|π|≡D|≡2|≡.|9|1[Sieve.]|9If |εS[i,|4k|βi)|4α≡↓|41λ|πfor 
 4850  |ε*5←4|¬E|4∪|4|¬ES4⊃,,|π∩o tonszeq D**#['↓J3}|≡D|≡3|≡.|9|1[Ste
 4852  p |εx.]]9Set |εx|4|¬L|4)|4α"↓*441,λ|[≤fd |ε*2Kβi|4←¬}P4(k|βiI4
 4855  α_↓*441*2n|πmod |εm|βi |πfor |ε1|4|¬E|4i|4|¬E|4r, 
 4859  |πand return tonsteppnD2.|]N'''''''''''*?*?*?and 
 4862  return to step D2.|'{A3}|≡D|≡4|≡.|9|1[Test |εx|g2|4α_↓|4N.]|
 4867  9|πSet |εy|4|¬L|4|"l|¬H|v4x|g2|4α_↓|4N|)|1|"L 
 4869  |πor to |ε|"l|¬H|v4x|g2|4α_↓|4N|)|1|"L. |πIf 
 4873  |εy|g2|4α=↓|4x|g2|4α_↓|4N, |πthen |ε(x|4α_↓|4y) 
 4876  |πis the desired factor, and the algorithm terminates. 
 4884  Otherwise return to step D3.|'|'{IC}{H10L12}{IC}!|9|4|1|1|1T
 4890  here are several ways to make this procedure 
 4898  run fast. For example, we have seen that if |εN 
 4908  |πmod 3|4α=↓|42, |πthen |εx |πmust be a multiple 
 4916  of 3; we can set |εx|4α=↓|43x|¬S, |πand use a 
 4925  di=erent sieve corresponding to |εx|¬S, |πincreasing 
 4931  the speed by a factor of 3. If |εN |πmod 3|4α=↓|41, 
 4942  |εx |πmust be congruent to |→|¬N (modulo 9), 
 4950  sb we cjf rkfntwb sue¬ess(↔or |≥)F¬F |πafdn|εx|¬C, 
 4957  |πεhere |εx|4α=↓|49)|¬S|4α+↓|41 |π_nd |ε)S4α=↓|49)|¬C|4α≠↓|4
 4960  1)↔|πto increase thesspeedfby a factor of 4|f1|d32|). 
 4967  If |ε] |π.mbf444α≡43#,|["hefn|≥*2x|[.¬uyhxb aumkqlippe 
 4971  off4λand the speed is increased by an additionaw 
 4979  factor of 4; in the other case, when |εxs|πmod 
 4988  4|4α=↓|41, |εx |πmust be odd so the speedfmjysbdsdbk∧∧ed. 
 4996  Anoohejnway tondouble the speed of the algorithm 
 5003  (at the expensesoffstora∧jsspacj)↔iushoncombicfspairssmf 
 5006  moduli, using |εm|βr|βα_↓|βkm|βk |πccnppace oxf|≥*2Mβkk|[(xgc
 5010  |≥*5544¬{U4≡K44}}Q44F4f↓36)*2#[,'!|:Y44555414[↓kns¬dfnmmgjsivp
 5010  vrgwkmhmxzhmbfmxfsqqedkcvvuqpUWgggcphmmCciushomuusshhys]`αBo
 5010  gwaknmvqjjwpvmf↔',fb¬kffmmnmmxyhxknaj¬ycvmvuqzjk).Paz 
 5011  uusuusu¬xsfxgcsx¬¬vpwshhqwh|¬¬M¬¬I¬¬xiusuuxkckj¬ycgmvqqzjcqq
 5011  phh73∞x¬pysper word. The tables |εS[i,|4k|βi] 
 5016  |πcan be kept in memorx wuth one b¬phper enor¬;?thuss3πλvalu
 5024  es can bdsszoredficna sucvgasword),The opejjzion 
 5029  |¬a|¬fN¬d↔λwhicm rdqlacdssthe |≥kFπ"hhxkt offthesakckxkwawor
 5032  nbxszejo iffhhes|ε≡K["h but offuusqekc=_dfwbrjfin 
 5036  mxxmgx isszejo,,fbrn|ε1←4|¬E|4k|4|¬ES430, |πcan 
 5039  be ussdftonpvgcdsss73λv¬wuassmxf|≥*2x|[≤z omck*3?Forncvnvdfcuf
 5041  cd↔,qwscjknm¬kksse¬jjjwicopiassoffthystab∧wss|ε*3[/,]4≡**,|π↔b
 5041  nhhuz thestab∧essfmrcessfxgc|≥*2Nβii|[/nvogvjslcm(|ε)Nβi,|43π
 5042  )↔|πbits;?thefnhhessuu¬¬sta∧∧wssfxrnsakv modkwuus=εliuknicmz
 5043  ∧gjwink¬xbjcmxfq∧gjf).Ukfdjchhysssuusu¬vppvmf↔,73∞sxxkkqpvmf
 5043  smxfhhysm¬ucnpgovpicnAwgggcthmnFfujj equuvaleft 
 5045  to code of the following form:|'|'{H9L11|h|∂4¬d|¬↑2|∂←¬j|¬3←
 5052  ¬n|¬n∨|∂|¬s|¬1|¬,!!|∂If|4rI1|4|¬W|40,|4set|4rI1←4|¬L|4rI1|4α
 5052  +↓|4lcm(|εm|β1,|422).←E|n|;|L|π|¬d|¬2|L|¬l|¬d|¬1|L|¬k|¬1←LrI
 5053  1←4←¬{|4←ε≡F=|β1|¬S.>|L|L|π|¬l|¬d|¬aUL|¬sS¬↓4¬↔]¬↓4PrJU4←¬}P
 5054  44≥\S¬}(77]44[3C57[7∂|PPPP¬¬F¬¬S¬¬C¬5P|¬↓←LrC1|4|¬{I4rC1←4↓≠
 5054  ↓|41.2⊗|L|L|¬jF¬4¬n|¬nNL{J1}α/↓|≤%|¬2>|L|L|¬i|¬n|¬c|¬1|L|¬m|
 5055  ¬1|LIf|4rI1|4|¬W|40,|4set|4rI1|4|¬L|4rI1|4α+↓|4lcm(|εm|β1,|4
 5055  30).>|L|L|π|¬sS¬t|¬1|L|¬k|¬1←L|εk|=|β1|¬S|4←¬W|4|πrI1.>
 5057  |L|L|¬l|¬dF¬1|L|¬k|¬2|LrI1|4|¬L|4|εk|=|β2|¬S.>
 5058  |L|L|π|¬a|¬kN¬d|L|¬f|¬2|¬,|¬1←LrA|4|¬{|4rA|42`≠fd'']44\*/S¬F(
 5058  7/]44π⊃C57.6∂|PPPI¬¬F¬kS}¬C¬|L|¬↓4LrC5444}}P4/C544≤↓45#7>
 5059  |L|L|¬¬K¬↓←¬kN¬¬NP{J↓*2***2↑*/¬↑2∂|PIPI¬c|¬nN¬kC¬4LI¬¬N¬6PIfF4/C
 5059  554|¬{Q45.]4?szH4/C5544¬}P46C554~↓4∀vv)(≥*2Mi2/,473))7>
 5060   PPPPM[}¬s}¬hN¬5|PV¬kN¬2|L|*2k|=|β2N¬S|4|¬L|4|πrI1.>
 5062  |PIP7[47[4#7>|PPPP¬¬S¬¬H}*25PP}}K}¬CPP\*2k*/*/IrC}}S44}}P44[3C57
 5063  7>|L|L|¬i|¬n|¬c|*?{U0}{H10L12M29}|πW58320#Computer 
folio 492 galley 8
 5065  Programming!ch. 4!f. 492!g. 8|'{A6}!|9|4|1|1|1If 
 5070  the table entries for |εm|βi |πdo not come out 
 5079  to be an integral number of words, further shifting 
 5088  of the table entries would be necessary on each 
 5097  iteration so that the bits are aligned properly. 
 5105  This would add quite a lot of coding to the main 
 5116  loop and it would probably make the program too 
 5125  slow to compete with Algorithm C unless |εv/u|4|¬E|4100 
 5133  |π(see exercise 7).|'!|9|4|1|1|1Sieve procedures 
 5138  can be applied to a variety of other problems, 
 5147  not necessarily having much to do with arithmetic; 
 5155  a survey of these techniques has been prepared 
 5163  by Marvin C. Wunderlich, |εJACM |π|≡1|≡4 (1967), 
 5170  10<19.|'!|9|4|1|1|1Special sieve machines (of 
 5175  reasonably low cost) have been constructed by 
 5182  D. H. Lehmer and his associates over a period 
 5191  of many years; see for example |εAMM |π|≡4|≡0 
 5199  (1933), 401<406. |πLehmer's electronic delay-line 
 5204  sieve which began operating in 1965 processes 
 5211  one millivmnnumbers per second; thus, each iteration 
 5218  of the loop in Algorithm D can be performed in 
 5228  one mvccgxecond on this device. Another way to 
 5236  factor sieves is described by D. H. and Emma 
 5245  Lehmer in |εMath. Comp. |π|≡2|≡8 (1974), 625<635.|'
 5252  |'|≡T|≡e|≡s|≡t|≡i|≡n|≡g |≡f|≡o|≡r |≡p|≡r|≡i|≡m|≡a|≡l|≡i|≡t|≡
 5255  y|≡.|9|4None of the algorithms we have discussed 
 5262  so far is an e∃cient way to determine that a 
 5272  large number |εn |πis prime. Fortunately, there 
 5279  are other methods available for settling thiusquestion; 
 5286  e∃cient methods for this purpose have been devised 
 5294  by |=⊂E. Lucas and others, notably D. H. Lehmer 
 5303  [see |εBulletin Amer. Mazh. Soc.λ|π|≡3|≡3 (1927), 
 5309  327<340].|'!|9|4|1←1|1According to Fermat's theorem 
 5314  (Theorem 1.2.4F)↔λ|εx|gp|gα_↓|g1 |πmod |εp|4α=↓|41λ|πif 
 5318  |εp |πis prime and if |εx |πcs noo asmultiple 
 5327  of |ε≥#.|πFurthermore, there are e∃cient ways 
 5333  to calculate |εx|gn|gα_↓|g1 |πmod |εn, |πrequiring 
 5339  only |εO(|πlog|4|εn) |πoperations of multiplication 
 5344  mod |εn. |π(We shall study these in Section 4.6.3 
 5353  below.) Therefore we can often determine that 
 5360  |εn |πis |εnot |πprime when this relationship 
 5367  fails.|'!|9|4|1|1|1For example, Fejrmat vvvvvvv*?*?*?*?!|9|4|1|1
 5371  |1For example, Fermat veri_ed that the numbers 
 5378  2|g1|4α+↓|41, 2|g2|4α+↓|41, 2|g4|4α+↓|41, 2|g8|4α+↓|41, 
 5382  and 2|g1|g6|4α+↓|41 are prime. In a letter to 
 5390  Mersenne written in 1640, Fermat conjectured 
 5396  that |ε2|g2|in|4α+↓|41 |πis always prime, but 
 5402  said he was unable to determine de_nitely whether 
 5410  4294967297|4α=↓|42|g3|g2|4α+↓|41 |πis a prime 
 5414  or not. We can compute 3|g2|i3|i2 mod (2|g3|g2|4α+↓|41) 
 5422  by using 32 operations of squaring a number modulo 
 5431  2|g3|g2|4α+↓|41, and the answer is 3029026160; 
 5437  therefore (by Fermat's own theorem, which he 
 5444  discovered in the same year 1640*3) we know that 
 5453  2|g3|g2|4α+↓|41 is |εnot |πprime. This argument 
 5459  giv¬ssus absolutely no idea what the factors 
 5466  are, but it answers Fermat's question.|'!|9|4|1|1|1Fermat's 
 5473  theorem is a powerful test for showing that |εn 
 5482  |πis not a prime. When |εn |πis not prime, it 
 5492  is always possible to _nd a value of |εx|4|¬W|4n 
 5501  |πsuch that |εx|gn|gα_↓|g1 |πmod |εn|4|=|↔6α=↓|41; 
 5506  |πexperience shows that in fact such a value 
 5514  can almost always be found very quickly. There 
 5522  are some rare values of |εn |πfor which |εx|ε|gn|gα_↓|g1 
 5531  |πmod |εn |πis frequently equal to unity, but 
 5539  then |εn |πhas a factor less than |=|g3|¬H|v4|εn|)|1; 
 5547  |πsee exercise 9. One example is |εn|4α=↓|43|4|¬O|411|4|¬O|4
 5553  17|4α=↓|4561; |πhere |ε|≤l(n)|4α=↓|44[lcm(2,|410,|416)|4α=↓|
 5555  480 in the notation of Eq. 3.2.1.2<9, so |εx|g8|g0 
 5564  |πmod 561|4α=↓|41|4α=↓|4|εx|g5|g6|g0 |πmod 561 
 5568  whenever |εx |πis relatively prime to 561.|'!|9|4|1|1|1The 
 5576  same method can be extended to prove that a large 
 5586  prime number |εn |πreally |πis |πa prime, by 
 5594  using the followingnikda: |ε|πusingnthe folllowinnusing 
 5599  the following idea: |ε|πusing the following idea: 
 5606  |εIf there is a number x for which the order 
 5616  of x modulo n is equal to |εn|4α_↓|41, then n 
 5626  is prime. |π(The order of |εx |πmodulo |εn |πis 
 5635  the smallest positive integer |εk |πsuch that 
 5642  |εx|gk |πmod |εn|4α=↓|41; |πsee Section 3.2.1.2.) 
 5648  For this condition implies that the numbers |εx|gk|4|πmod|4|
 5655  εn |πfor |ε1|4|¬E|4k|4|¬E|4n|4α_↓|41 |πare distinct 
 5660  and relatively prime to |εn, |πso they must be 
 5669  the numbers 1, 2,|4.|4.|4.|4, n|4α_↓|41 |πin 
 5675  some order; thus |εn |πhas no proper divisors. 
 5683  If |εn |πis prime, such a number |εx (|πa ``primitive 
 5693  root'' of |εn) |πwill always exist; see exercise 
 5701  3.2.1.2<16. In fact, the number of such primitive 
 5709  roots is rather numerous; there are |ε|≤'(n|4α_↓|41) 
 5716  |πof them.,ukff|εn/←≤-(n|4α_↓|41)|4α=↓|4O(|πlog|4log|4|ε≡).|
 5717  '!|9|4|1|1|1|ε|πIt is unnecessary to calculate 
 5723  |εx|gk|4|πmod|4|εn |πfor all |εk|4|¬E|4n|4α_↓|41 
 5727  |πto determine ifnthe order of |εx |πis |εn|4α_↓|41 
 5735  |πor not. The order of |εx |πwill be |εn|4α_↓|41 
 5744  |πif and only if|'{A6}|ε!|9|4|1|1←1|4|1|πi)|9|εx|gn|gα_↓|g1|
 5748  4|πmod|4|ε↔|4α=↓|414'!|9|4|1|1←1←π∪i)|9←ε)Fg(*4gn|gα_↓|g1|g*2(
 5748  v/|gp|4|πmod|4|εn|4|=|↔6α=↓|41 |πfor all primes 
 5752  |εp |πwhich divide |εn|4α_↓|41.|'{A6}Nπ*1Fbr |εx|gkS4←π.odF4←
 5757  ε,N4α=↓|41λ|πif afd onlysif |εs |π∪s a multiple 
 5764  of the order of |εx |πmodulo |εn. |πIf the two 
 5774  conditions hold, andfif |εk |πis the order of 
 5782  |εx |πmodulo |εn, |πwe therefore know that |εk 
 5790  |πis a divisor of |εn|4α_↓|41, |πbut not a divisor 
 5799  of |ε(n|4α_↓|41)/p |πfor any prime factor |εp 
 5806  |πof |εn|4α_↓|41; |πso |εk |πmust be equal to 
 5814  |εn|4α_↓|41. |πThis completes the prooffhhat 
 5819  conditions (i) and (ii) su∃ce to establish the 
 5827  prcmjlity ofn|εn.|'|π!|9|4|1|1|1Exercise 10 shows 
 5832  that we may in fact use di=erent values of |εx 
 5842  |πfor each prime |εp, |πand |εn |πwill still 
 5850  be prime. We may restrict consideration to primes 
 5858  |εx, |πsince the order of |εuv |πmodulo |εn |πdivides 
 5867  the least common multiple of the orders of |εu 
 5876  |πand |εv |πby exercise 3.2.1.2<15. Conditions 
 5882  (i) and (ii) can be tested e∃ciently by using 
 5891  the rapid methods for evaluating powers oxfiunumbercdiscusse
 5897  d in Section 4.6.3. But it is necessary to know 
 5907  the prime factors of |εn|4α_↓|41, |πso we have 
 5915  an interesting situation in which the factorization 
 5922  of |εn |πdepends on that of |εn|4α_↓|41*3|'|π|≡A|≡n 
 5930  |≡e|≡x|≡a|≡m|≡p|≡l|≡e|≡.|9|4The study of a reasonably 
 5935  typical large factorczation will help to _x the 
 5943  ideas we have discussed so fjr. Lez uustryston=≡dfthespccmes
 5950  fkkgorksoff26v36g3|g6←4α+↓|41. The factorization 
 5953  of this 65-digit number can be initiated by noticingv 
 5962  t*?*?*?*?t|]≤{K2|g2|g1|g4|4α+↓|41|4α=↓|4(2|g1|g0|g7|4α_↓|42|g5|g
 5962  4|4α+↓|41)(2|g1|g0|g7|4α+↓|42|g5|g4|4α+↓|41);|J!(14)|;
 5963  {A6}|πthis identity is a special case of some 
 5971  factorizations discovered by A. Aurifeuille in 
 5977  1873 [see Dickson's |εHistory, |π|≡1, p. 383]. 
 5984  We may now examine each of the 33-digit factorfsin 
 5993  (14).]'!|9|4|1|1|1A computer program readily 
 5997  discovers that 2|g1|gπ←g7|4α_↓|42←g5←g4|4α+↓|41|4α=↓|45|4|¬O
 5999  |4857|4|¬O|4|εn|β0, |πwhere|'{A6}|εn|β0|4α=↓←4378**6899961660
 6001  0577662392733α6J∨(35)N;{J6}Sπ⊗is a 29-digit numberchaving 
 6005  no prime factors lesssthafn1000. A multiple-*2recision 
 6011  calculation using thes``binary method''λof Section 
 6016  4.6.3 syo∧s thawh|'{A6}|*?*?*?ε3|gn|r0|gα_↓|g1|4|πmod|4|εn|β0|4
 6019  α=↓|41,|;{A6}|πso we suspect that |εn|β0 |πis 
 6026  prime. It is certainly out of the question to 
 6035  prove that |εn|β0 |πis prime by trying the 10 
 6044  million million or so poteftial divisbgk↔nbkyhthesmxzhmdndis
 6049  kkssedsa∧bve givessa feasub∧e test for primjwity: 
 6055  okj nexb goaw isstonfjkvorc|ε≡Ni1→4≤↓45#.|[↓qphhppptlwsfk≥*2k
 6058  qly)naucgmputer program _↔ds that|'{A6}|εnNβ0|4α_↓*441|4α=↓|4
 6062  2|4|¬O|42|4|¬O|419|4|¬O|4107|4|¬O|4353|4|¬O|4n|β1,!!n|β1|4α=
 6062  ↓|41339127077551082260549*?*?*?*?Here |ε3|gn|r1|gα_↓|g1 
 6064  |πmod |εn|β1|4|=|↔6α=↓|41, |πso |εn|β1 |πis not 
 6070  prime; by continuing Algorithm A or Algorithm 
 6077  B we _nd |εn|β1|4α=↓|491813|4|¬O|4n|β2, n|β2|4α=↓|4143675413
 6081  657196977. |πThis time |ε3|gn|r2|gα_↓|g1 |πmod 
 6086  |εn|β2|4α=↓|41, |πso we will try to prove that 
 6094  |εn|β2 |πis prime. This requires the factorization 
 6101  |εn|β2|4α_↓|41|4α=↓|42|4|¬O|42|4|¬O|42|4|¬O|42|4|¬O|43|4|¬O|
 6101  43|4|¬O|4547|4|¬O|4n|β3, n|β3|4α=↓|41824032775457. 
 6103  |πSince |ε3|gn|r3|gα_↓|g1 |πmod |εn|β3|4|=|↔6α=↓|41, 
 6107  |πwe know that |εn|β3 |πis composite, and Algorithm 
 6115  A _nds that |εn|β3|4α=↓|41103|4|¬O|4n|β4, n|β4|4α=↓|41653701
 6119  519. |πThe number |εn|β4 |πbehaves like a prime 
 6127  (i.e., |ε3|gn|r4|gα_↓|g1 |πmod |εn|β4|4α=↓|41), 
 6131  |πso we calculate|'{A6}|εn|β4|4α_↓|41|4α=↓|42|4|¬O|47|4|¬O|4
 6134  19|4|¬O|423|4|¬O|4137|4|¬O|41973.|;{A6}|πThis 
 6136  is mokru≠st complete factorization; we are ready 
 6143  to backtrack to the previous subproblem, proving 
 6150  that |εn|β4 |πis prime)λThssfoglg∧qcvmvaluassajdsno∧ 
 6154  comvuted,λakcordingnto the prgcedkjdsof exercise 
 6158  10:|'←'|∂$!|∂$!!!|∂$!!!!!!|∂>!!!!!|∂4SS;&|>|εx|;
 6162  p|;x|ur(n|β4α_↓1)/p|)|)|4|πmod|4|εn|β4|;x|gn|r4|gα_↓|g1|4|πm
 6164  od|4|εn|β4|;>|>2|;!|9|1|1|12|;1|;(1)|;>|>2|;!|9|1|1|17|;
 6175  766408626|;(1)|;>|>2|;!|1|119|;332952683|;(1)|;
 6183  >|>2|;!|1|123|;1154237810|;(1)|;>|>2|;|9|1137|;
 6193  373782186|;(1)|;>|>2|;19777:490790919|;(1)|;>
 6201  |>3|;!|9|1|1|12|;1|;(1)|;>|>5|;!|9|1|1|12|;1|;
 6211  (1)|;>|>7|;!|9|1|1|12|;1653701518|;1|;>{A12}{H10L12}|π|π(Her
 6219  e ``(1)'' means a result of 1 which needn't be 
 6229  computed since it can be deduced from previous 
 6237  calculations.) Thus |εn|β4 |πis prime, and |εn|β2|4α_↓|41 
 6244  |πhas been completely factored. A similar ckwculation 
 6251  shows that |εn|β2 |πis prime, and this complete 
 6259  factorization of |εn|β0|4α_↓|41 |π_nally shows 
 6264  [after still another calculation like (16)] that 
 6271  |εn|β0 |πis prime.|'!|9|4|1|1|1The next quantity 
 6277  to be factored is the other half of (14),|'{A6}|εn|β5←4α=↓|4
 6286  2|g1|g0|g7|4α+↓|42|g5|g4|4α+↓|41.|;{A6}|πSince 
 6288  |ε3|gn|r5|gα_↓|g1|4|πmod|4|εn|β5|4|=|↔6α=↓|41, 
 6289  |πwe know that |εn|β5 |πis not prime, and Algorithm 
 6298  B shows that |εn|β5|4α=↓|4843589|4|¬O|4n|β6, 
 6302  n|β6|4α=↓|4192343993140277793096491917. |πUnfortunately, 
 6304  |ε3|gn|r6|gα_↓|g1 |πmod |εn|β6|4|=|↔6α=↓|41, 
 6307  |πso we are left with a 27-digit nonprime number. 
 6316  Continuing Algorithm B might well exhaust our 
 6323  patience (not our budget#nobody is paying for 
 6330  this, we're using idle time on a weekend). But 
 6339  the sieve method of Algorithm D will be able 
 6348  to crackk P*2Nβ6 |πinto its two factors.|'|Ha*?*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 6355  
folio 496 galley 9
    0  {U0}{H10L12M29}|πW58320#Computer|9Programming!ch. 
    1  4!f. 496!g. 9|'{A6}|≡I|≡m|≡p|≡r|≡o|≡v|≡e|≡d |≡p|≡r|≡i|≡m|≡a|
    5  ≡l|≡i|≡t|≡y |≡t|≡e|≡s|≡t|≡s|≡.|9|4Since the above 
    9  procedure for proving that |εn |πis prime requires 
   17  the complete factorization of |εn|4α_↓|41, |πit 
   23  will bog down for large |εn. |πAnother technique, 
   31  which uses the factorization of |εn|4α+↓|41 |πinstead, 
   38  is described in exercise 15; if |εn|4α_↓|41 |πturns 
   46  out to be too hard, |εn|4α+↓|41 |πmight be easier.|'
   55  !|9|4|1|1|1Signi_cant improvements have recently 
   59  been discovered. Brillhart, Lehmer, and Selfridge 
   65  [|εMath. Comp. |π|≡2|≡9 (1975), 620<647, exp. 
   71  Corollary 11] have developed aumethod which works 
   78  when |εn|4α_↓|41 |πand |εn|4α+↓|41 |πhave been 
   84  onlyspartiawly faktorjd(?Suqpvfss|\*2N4α_↓|41|4α=↓|4f|1|gα_↓r
   85  |gα≠↓↔|[≤kff|≥*2N4~↓4554*24↔F5←gα+↓⊃|gα+↓, |πwhere 
   87  we know the complete factorization of |εf|1|gα_↓ 
   94  |πand |εf|1|gα+↓, |πand we know that all factors 
  102  of |εr|gα_↓ |πand |εr|gα+↓ |πare |¬R|εb. |πIf 
  109  |εb|g3f|1|gα_↓f|1|gα+↓|4|πmax(|εf|1|gα_↓,|4f|1|gα+↓) 
  110  |πis greater than |ε2n, |πa small amount of additional 
  119  computation, described in their paper, will determine 
  126  whether or not |εn |πis prime. Therefore numbers 
  134  of up to 77∀digits can usually be tested for 
  143  primality in 2 or 3 seconds, simply by casting 
  152  out all prime factors |¬W30030 from |εn|4|¬9|41 
  159  [|πsee J. L. Selfridge andfM..C#.Qqkfdrlich, 
  164  |εProc. Fourth Manitoba Conf. Numej. Math. |π(194), 
  171  109<120]. |πThe partial factorizazion of other 
  177  quantities like |εn|g2|4|¬N|4n|4α+↓←41 |π_fd 
  181  |εnNg2|4α+↓**41λ|π/kknxbsuusdfton≡vvvgv¬shhissmxzhodnszpll 
  182  fkkghyjc[[..C#,Qqplpu¬f↔,|≥\vgc#nFkkbh Mancpoba 
  184  Conf)λNumer. Math. (1975), |πto appear].|'|π!|9|4|1|1|1In 
  190  practice, when |εn has no small prime factors 
  198  and |ε3|gn|gα_↓|g1|4|πmod|4←εn|4α=↓|41, |πit 
  201  has almost always tqkndd out that |εn |πis prime.n(One 
  210  of the raresexkdqtions is |ε,N4α=↓|4|f1|d37|)(2|g2|g<|4α≠↓|4
  214  9)|4α≡↓]42375544¬}M4163<*5#) |π3jj¬sL#.MVplwjchqusicv¬sypv∧wz
  215  dfhhpusppyfmmxfmm,,sym∧qcvvhhqwhqqyfn|≥*2n|[#usfkvvuu¬∧wsxxyu
  215  whpwauyhhw∧mfkuypccvhpvcvxsshhyjjsiusmv¬j∧qywvvcvvpvgb∧∧¬ppp
  215  yyhhqwhsxmxssx¬wlppvcvxs ≥≥q|π↓qpl violate a 
  219  slight strengthening of Fermat's test: Eithejc|ε≥SgcNg↓≠↓*4g3
  224  ←4←πmod|4←ε,|=←↔**α=↓*441 |πor there will bd somes|≥≡S4|¬JC41λ
  229  |πsukh thaz |≥↑]gkK¬JfN4↓↓455|[↓kff|≥*5544}}Q4/C4*24\QUur)(≤↓↓
  231  *2*266V¬K()|((44[[mbF44\*2N44}}Q46N4↓↓455 [↓kff|\≤cV3644[[mof|4
  232  Q*2n|6α≡I43. |πIn fact, if a well-known number-theoretic 
  239  conjecbe proved, there will be some such |εq|4|¬E|4c(|πln|4|
  246  εn)|g2, |πfor some constant |εc. [|π|εJ. Comp. 
  253  System Sci. |π|≡1|≡1 (1975), |πto appear.] If 
  260  number theorists succeed in proving su∃ciently 
  266  good explicit upper bounds for the least |εk|πth 
  274  power nonresidues modulo given primes, Miller's 
  280  approach would yield a practical algorithm for 
  287  testing primality in order (log|4|εn)|g5 |πsteps. 
  293  Alternatively it would su∃ce for practical purposes 
  300  to have a decent bound on |εq |πwhich works for 
  310  all |εn|4|¬W|410|g1|g0|g0, |πsay.|'|'|≡F|≡a|≡c|≡t|≡o|≡r|≡i|≡
  314  n|≡g |≡v|≡i|≡a |≡c|≡o|≡n|≡t|≡i|≡n|≡u|≡e|≡d |≡f|≡r|≡a|≡c|≡t|≡
  317  i|≡o|≡n|≡s|≡.|9|4The factorization procedures 
  320  we have discussed so far will often balk at numbers 
  330  of 30 digits or more, and another idea is needed 
  340  if we are to go much further. Fortunately there 
  349  is such an idea; in fact, there were two ideas, 
  359  due respectively to A. M. Legendre and M. Kraitchik, 
  368  which D. H. Lehmer and R. E. Powers used to devise 
  379  a new technique many years ago [|εBull. Amer. 
  387  Math. Soc. |π|≡3|≡7 (1931), 770<776]. However, 
  393  the method was not used at that time because 
  402  it wasscomparazivxwyhunfuupw∧gz fmgnfdskkckwckwwtogk)λThissn
  404  egjzpvd judgment prevailed until the late 1960?, 
  411  whennJommnBgcllhwjo foundfthat the Lehmer<5owers 
  415  approach ddserved to be resurrected, since it 
  422  was quiteswell-suited to computer programming. 
  427  In fact, he and Michael A. Morrison later developed 
  436  it into the current champion of all methods for 
  445  factoring large numbers: It handles typical 25-digit 
  452  numbers in about 30 seconds, and 40-digit numbers 
  460  in about 50 minutes, on an IBM 360/91 computer 
  469  [see |εMazh..Comp. |π|≡2|≡9 (1975), 183<205]. 
  474  In 1970 the method had its _rst triumphant success, 
  483  discovering that 2|g1|g2|g8|4α+↓|41|4α=↓|459649589127497217|
  485  4|¬O|45704689200685129054721.|'!|9|441←1←11hysbjsicniddasis|
  486  '{A6}|εn|β6←4α≡↓*348*5769*52677117←4←¬B|42352<\7α104401.];{J6}N
  487  π'Thissrjsuqlhcv¬q∧f|\*2moh|[[q¬¬sxbefnnfifcovdred 
  488  by Aggorithm A in a reasonable length of time; 
  497  a fdwumvplivmnipzjjwpvmfsmxfUWgggcphmmnXi∧¬qgd 
  499  probabpy have su∃ced.|''''''''''''''''''''''''''''''''''''''
  502  ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  502  ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  502  ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  502  ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  502  ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  502  ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  502  ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  502  ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  502  '''''*?*?*?*?!|9|4|1|1|1The calculations are complete; 
  506  the prime factorization of 2|g2|g1|g4|4α+↓|41 
  511  is|'{A6}|ε5|4|¬O|4857|4|¬O|4843589|4|¬O|48174912477117|4|¬O|
  512  423528569104401|4|¬O|4n|β0,|;{A6}|πwhere |εn|β0 
  515  |πis the 29-digit prime in (15). A certain amount 
  524  of good fortune entered into these calculations, 
  531  for if we had not started with the known factorization 
  541  (14) it is quite probable that we would _rst 
  550  have cast out the small factors, reducing |εn 
  558  |π+o |εn|β6n|β0; |πthis 55-|πdigit number would 
  564  have been much more di∃cult to factor#Algorithm 
  571  D would be useless and Algorithm B would have 
  580  to work overtime because of the high precision 
  588  necessary.|'!|9|4|1|1←1Dozens of further numerical 
  593  examples can be found in an article by John Brillhart 
  603  and J. L.λSelfridgd, |εMath. Comp. |π|≡2|≡1 (1967), 
  610  87<96.|'!|:*34←1|51|1Tysbasicnidea is to search 
  615  for numbers |εx |πand |εy |πsuch that|'{A6}|εx|g2|4|"o|4y|g2
  622  |4(|πmodulo|4|εN),!!0|4|¬W|4x,|4y|4|¬W|4N,!!x|4|=|↔6α=↓|4y,!
  622  !x|4α+↓|4y|4|=|↔6α=↓←4].|J!(17)|;{A6}|πFermat's 
  624  mdzhodfivvgxssshhyssygong∧jccjquurjxxfmh|≥*2Fg3N4↓≠↓*44;Sv3]4(
  624  *2↓N4],λ|π~kz actually thescongruence (17) is 
  629  enough to split |εN |πinto factors: It implies 
  637  that |εN |πis a divisor of |εx|g2|4α_↓|4y|g2|4α=↓|4(x|4α_↓|4
  643  y)(x|4α+↓|4y), |πyet |εN |πdivides neither |εx|4α_↓|4y 
  649  |πnor |εx|4α+↓|4y; |πhence gcd(|εN,|4x|4α_↓|4y)λ|π_nd 
  653  gcd(|εN,|4)|4α+↓|4y) |πare proper factors ofs|εN 
  658  |πwhich can be found by Euclid's algorithm.|'
  665  |π$|9*3441←1←13nfswaystonfkukgvdjcsxgqqpvmfsmxf(7*2)iushompgok
  665  kfxgcv¬wqussmxf|\*2x|[)ukvhhhqwh|≥*2Xg2]44""N4_s(←π.mbkwgn|ε)↔
  665  ,|[)xrcsxkwlpv¬wuassmxf|≥\¬}jU¬}7.|[↓usqwsqqplpsse↔,iphiusmx
  665  xzfnuusuvvle mattej to piukjstogdzhej sbguqivmfsmxfhhiuscvmv
  669  gkufckshommbbwucnsxgqqpvmfsmxf)7).NM∧qikf|≥*2XV364*2**4_U4~↓4≡K
  669  fFv3/|π)xgcsxmes|≥*2k|π≠kdf|ε≠↔,|[≤qphhsx¬wlp|ε≥N¬GU¬G, 
  670  |π"he fraction |εx/d |πis a good approximation 
  677  to |¬H|v4←εkN|)←1|1;λ|π/onversewq↔,if |ε)≡-f|π/s 
  680  an esqekially good approximation to |¬H|v4|εkN|)|1|1, 
  686  |¬Gx|g2|4α_↓|4kNd|g2|¬G |πεill be small.λThis 
  690  observation suggests looking at the continued 
  696  fraction expansion of |¬H|v4|εkN|)|1|1, |π↔ucce 
  701  weshq¬d sses(<q)λ4#7#3↓↓3)↔thaz conopckud frjkvigns 
  705  yuawd goodfrationjwiaqproxumazions.|''⊗!|::44555557Vmmpckudf
  707  fkjkvpvmfsfxgcqqujjjwpccicrjwpvmkwpppusshp¬¬sm¬kxy 
  708  plauukmh propdrties, which are proved in exercise 
  715  4.5.3<12. The algorithm below makes use of these 
  723  propejoiesstonddjcvkssxgqwivmfshomhhsscvmvgkufckS]↓{**}\εxXV3
  723  644["M4(→(≤↓↓(V∧SC35PUkjsIβ15)5(*2PUkjSI⊃6X*26((44}¬MI4}¬M44}¬
  723  M45p|krsIcmN)m|)|4(|πmodulo|4|εN).|J!(18)|;{A6}|πHejdswasuus
  724  suu=*2xdfsszhmxfsx¬wlppvcvxss \≥PI154*2466,pPI⊃6I*2477,47[4s 
  726  will never be factors of the numbers generated 
  734  bx the algorithm (see exercise 14). If (|εx|β1,|4e|β0|β1,|4e
  741  |β1|β1,|4.|4.|4.|4, e|βm|β1),|4.|4.|4.|4, (x|βr,|4e|β0|βr,|4
  743  e|β1|βr,|4.|4.|4.|4, e|βm|βr) |πare solutions 
  747  of (18) such that the vector sum|'{A6}|ε(e|β0|β1,|4e|β1|β1,|
  754  4.|4.|4.|4,|4e|βm|β1)|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4(e|β0|βr,|4e
  754  |β1|βr,|4.|4.|4.|4,|4e|βm|βr)|4α=↓|4(2e|=|β0αO↓,|42e|=|β1αO↓
  754  ,|4.|4.|4.|4,|42e|=|βmαO↓)!(19)|?{A6}|πis |εeven 
  757  |πin each component, then|'{A6}|εx|4α=↓|4(x|β1|4.|4.|4.|4x|β
  761  r)|4|πmod|4|εN,!!y|4α=↓|4|≥1(|→α_↓1)|ure|β0|)|)p|ure|β1|)1|)
  761  |4.|4.|4.|4p|ure|βt|)m|))|4|πmod|4|εN|J!(20)|;
  762  {A6}|πyields a solution to (17), except for the 
  770  possibility that |εx|4|"o|4|→|¬Ny. |πCondition 
  774  (19) essentially says that the vectors are linearly 
  782  dependent modulo 2, so we must have a solut{U0}{H10L12M29}|π
folio 500 galley 10
  790  W58320#Computer|9Programming!ch. 4!f. 500!g. 
  793  10|'{A6}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m |≡E (|εFactoring 
  797  via continued fractions).|9|πGiven a positive 
  802  integer |εN |πand a positive integer |εk |πsuch 
  810  that |εkN |πis not a perfect square, this algorithm 
  819  attempts to discover solutions to the congruence 
  826  (18) for _xed |εm, |πby analyzing the convergents 
  834  to the continued fraction for |ε|¬H|v4kN|)|1|1. 
  840  |π(Another algorithm, which uses the outputs 
  846  to discover factors of |εN, |πis the subject 
  854  of exercise 12.)|'{A6}{I1.9H}|≡E|≡1|≡.|9[Initialize.]|9Set 
  858  |εD|4|¬L|4kN, R|4|¬L|4|"l|¬H|v4D|)|1|"L, R|¬S|4|¬L|42R, 
  861  U|4|¬L|4u|¬S|4|¬LR|¬S, V|4|¬L|41, V|1|¬S|4|¬L|4D|4α_↓|4R|g2,
  863   P|4|¬L|4R, P|¬S|4|¬L|41, A|4|¬L|40, S|4|¬L|40. 
  868  |π(This algorithm follows the general procedure 
  874  of exercise 4.5.3<12, _nding the continued fraction 
  881  expansion of |ε|¬H|v4kN|)|1. |πThe variables 
  886  |εU, U|¬S, V, V|1|¬S, P, P|¬S, A, S |πrepresent, 
  895  respectively, what that exercise calls |εR|4α+↓|4*/Uβn, 
  901  R|4α+↓|4U|βn|βα_↓|β1, V|βn, V|βn|βα_↓|β1, p|βn 
  905  |πmod |εN, p|βn|βα_↓|β1 mod |εN, A|βn, |πand 
  912  |εn |πmod 2. We will always have |ε0|4|¬W|4V|4|¬E|4U|4|¬E|4R
  919  |¬S, |πso the highest precision is needed only 
  927  for |εP |πand |εP|¬S.)|'{A3}|π|≡E|≡2|≡.|9[Step 
  932  |εU, V, S.]|9|πSet |εT|4|¬LH47, V|4←¬L|4A(U|¬S|4α_↓|4U)|4α+↓
  936  |4V|1|¬}F,nV|5¬S|4|¬L|4T, A|4|¬L|4|"l(R|4α+↓|4U)/V|"L, 
  938  U|¬S|4|¬L|4U, U|4|¬L|4R|¬S|4α_↓|4(U|4|πmod|4|εV), 
  940  S|4|¬L|41|4α_↓|4S.|'{A3}|π|≡E|≡3|≡.|9[Factor 
  942  |εV.]|9|π(Now we have |εP|g2|4α_↓|4kNQ|g2|4α=↓|4(|→α_↓1)|gSV
  945  , |πfor some |εQ |πrelatively prime to |εP, |πby 
  954  exercise 4.5.3(c).|≥2 Set |ε(e|β0,|4e|β1,|4.|4.|4.|4, 
  958  e|βm)|4|¬L|4(SF,|||444444444*?*?*? exercise 4.5.3(c).|≥2 
  961  Set |ε(e|β0,|4e|β1,|4.|4.|4.|4, e|βm)|4|¬L|4(S,|40,|4.|4.|4.
  963  |4,|40), T|4|¬L|4V. |πNow do the following, for 
  970  1|4|¬E|4|εj|4|¬E|4m: |πIf |εT |πmod |εp|βj|4α=↓|40, 
  975  |πset |εT|4|¬L|4T/p|βj |πand |εe|βj|4|¬L|4e|βj|4α+↓|41, 
  979  |πand repeat this process until |εT |πmod |εp|βj|4|=|↔6α=↓|4
  986  0.|'{A3}|π|≡E|≡4|≡.|9[Solution?]|9If |εT|4α=↓|41, 
  989  |πoutput the values |ε(P,|4e|β0,|4e|β1,|4.|4.|4.|4,|4e|βm), 
  993  |πwhich comprise a solution to (22). (If enough 
 1001  solutions have been generated, we may terminate 
 1008  the algorithm now.)|'{A3}|≡E|≡5|≡.|9[Step |εP, 
 1013  P|¬S.]|9|πIf |εV|4|=|↔6α=↓|41 |πor |εU|4|=|↔6α=↓|4R|¬S, 
 1017  |πset |εT|4|¬L|4P, P|4|¬L|4(AP|4α+↓|4P|¬S) |πmod 
 1021  |εN, P|¬S|4|¬L|4T. |πOtherwise the continued 
 1026  fraction process has started to repeat its cycle, 
 1034  except perhaps for |εS, |πso the algorithm terminates. 
 1042  (The cycle will usually be so long that this 
 1051  doesn't happen, unless |εkN |πis nearly a perfect 
 1059  square. For the length of cycle, cf. D. R. Hickerson, 
 1069  |εPaci⊂c J. Math. |π|≡4|≡6 (1973), 429<432; D. 
 1076  Sharks, |εProc. Boulder Number Theory Conference 
 1082  (|πU. of Colorado: 1972), 217<224.)|'|'{IC}!|9|4|1|1|1Best 
 1089  results will occur, of course, when |εk |πand 
 1097  |εm |πare chosen appropriately. A large value 
 1104  of |εk |πmakes the |εV |πnumbers larger (hence 
 1112  less likely to factor), while a good value of 
 1121  |εk |πmakes them divisible by more small primes 
 1129  (hence more likely to factor), so we want to 
 1138  balance these tendencies. Consider, for example, 
 1144  the divisibility of |εV |πby powers of 5. We 
 1153  have |εP|g2|4α_↓|4kNQ|g2|4α=↓|4(|→α_↓1)|gSV |πin 
 1156  step E3, so if 5 divides |εV |πwe have |εP|g2|4|"o|4kNQ|g2 
 1166  (|πmodulo 5). Here |εQ |πcannot be a multiple 
 1174  of 5, since it is relatively prime to |εP, |πso 
 1184  we may write |ε(P/Q)|g2|4|"o|4kN. |πIf we assume 
 1191  that |εP |πand |εQ |πare random relatively prime 
 1199  integers, so that the 24 possibilities of (|εP 
 1207  |πmod 5, |εQ |πmod 5)|4|=|↔6α=↓|4(0,|40) are 
 1213  equally likely, the probability that |ε5|¬DV 
 1219  |πis therefore |f4|d324|), |f8|d324|), 0, 0, 
 1225  or |f8|d324|) according as |εkN |πmod 5 is 0, 
 1234  1, 2, 3, or 4.mSimilarly the probability that 
 1242  |ε25|¬DV |πis 0, |f40|d3600|), 0, 0, |f40|d3600|) 
 1249  respectively, unless |εkN |πis a multiple of 
 1256  25. In general, given an odd prime |εp |πwith 
 1265  (|εkN)|ur(pα_↓1)/2|)|) |πmod |εpα=↓1, |πwe _nd 
 1270  that |εV |πis a multiple of |εp|ge |πwith probability 
 1279  |ε2/p|ge|gα_↓|g1(|1p|4α+↓|41); |πand the average 
 1283  number of times |εp |πdivides |εV |πcomes to 
 1291  |ε2p/(|1p|g2|4α_↓|41). |πThis analysis, suggested 
 1295  by R. Schroeppel, suggests that the best choice 
 1303  of |εk |πis that which maximizes|'{A2}|ε|↔k|uc|)p|1|1|1|πpri
 1309  me|)|4|εf(|1p,|4kN)|4|πlog|4|εp|4α_↓|4|f1|d32|)|4|πlog|4|εk,
 1309  |J!(18)|;{A6}|πwhere |εf |πis the function de_ned 
 1316  in exercise 13, for this is essentially the expected 
 1325  value of the logarithm of |ε|¬H|v4N|)/T |πwhen 
 1332  we reach step E4.|'!|9|4|1|1|1Before we study 
 1339  the choice ov |εm, |πlet us consider an important 
 1348  re_nement of Algorithm E: Comparing step E3 with 
 1356  Algorithm A, we see that the factoring of |εV 
 1365  |πcan stop whenever we _nd |εT |πmod |εp|βj|4|=|↔6α=↓|40 
 1373  |πand |ε|"lT/p|βj|"L|4|¬E|4p|βj, |[(unce |εT 
 1377  |πwill then be 1 or prime. If |εT |πis a prime 
 1388  greater than |εp|βm (|πit will be at most |εp|βm|g2|4α+↓|4p|
 1396  βm|4α_↓|41) |πwe can still output (|εP,|4e|β0,|4.|4.|4.|4, 
 1402  e|βm, T), |πsince a complete factorization has 
 1409  been obtained. The second phase of the algorithm 
 1417  will use only those outputs whose prime |εT'|πs 
 1425  |πhave occurred at least twice. This modi_cation 
 1432  gives the e=ect of a much longer list of primes, 
 1442  without increasing the factorization time.|'!|9|4|1|1←1]ow 
 1448  lez'? makesa heurcstic analysis of the running 
 1455  time of Algorithm E, following unpublished ideas 
 1462  of R. Schroeppel: We assume that |εk|4α=↓|41, 
 1469  |πto get an upper bo¬kf) The number of outputs 
 1478  needed to produce a factorization of |εN, |πusing 
 1486  the modi_cation in the preceding paragraph, will 
 1493  be roughly proportional to |ε|≤p(p|βm|g2)|4|¬V|4(m/|πlog|4|ε
 1497  m)|g2, |πlet's say |εm|g2. |πEach execution of 
 1504  step E3 will take about order |εm |πunits of 
 1513  time; and if we assume that |εV |πis randomly 
 1522  distributed between 0 and |ε2|¬H|v4N|) |πour 
 1528  chance of successful output per iteration will 
 1535  be approximately |εF|≥1(|πlog|4|εp|βm|g2)/(|πlog|42|ε|¬H|v4N
 1537  |)|1)|≥2, |πwhere |εF |πis Dickman's function 
 1543  of Fig. 11. Therefore the total running time 
 1551  is roughly proportional to|'{A6}|ε|εm|g3/F(1/|≤a),!!|≤a|4α=↓
 1555  |4(|πlog|4|ε2|¬H|v4N|)|1)/(|πlog|4|εp|βm|g2).|J!(19)|;
 1556  {A6}|πIt is possible to show that |εF(1/|≤a)|4α=↓|4|πexp(|ε|
 1562  →α_↓|≤a|4|πln|4|ε|≤a|4α+↓|4O(|≤a|4|πlog|4log|4|ε|≤a)|≥2 
 1563  |πaus |ε*?*?It is possible to show that |εF(1/|≤a)|4α=↓|4|πexp
 1570  (|ε|→α_↓|≤a|4|πln|4|ε|≤a|4α+↓|4O(|≤a|4|πlog|4log|4|ε|≤a)|≥2 
 1571  |πas |ε|≤a|4|¬M|4|¬X; |πin fact, N. G. de Bruijn 
 1579  [|εJ. Indian Math. Soc. |π|≡1|≡5 (1951), 25<32] 
 1586  has obtained a much sharper estimate. If we now 
 1595  choose ln|4|εm|4α=↓|4|¬H|v4(|πln|4|εN)(|πln|4ln|4|εN)/24|) 
 1597  |πwe _nd that (19) becomes exp(|¬H|v4|f3|d32|)(ln|4|εN)(|πln
 1602  |4ln|4|εN)|)|4α+↓|4O|≥1(|πlog|4|εN)|g1|g/|g2(|πlog|4log|4|εN
 1602  )|gα_↓|g1|g/|g2(|πlog|4log|4log|4|εN)|≥2. |πNote 
 1604  that the running time is order |εN|g|≤o|g(|gN|g), 
 1611  |πwhere |ε|≤o(N)|4|¬V|4|¬H|v4|f3|d32|)(|πln|4ln|4|εN)/(|πln|
 1612  4|εN)|) |πgoes to 0 as |εN|4|¬M|4|¬X*3 |πThese 
 1619  asymptotic formulas are too crude to be applied 
 1627  for |εN |πin a practical range, however; several 
 1635  years' experience by Morrison and Brillhart suggests 
 1642  that |εm |πshould be approximately 25(log|β1|β0|4|εN|4α_↓|41
 1647  4) |πfor 10|g2|g5|4|¬W|4|εN|4|¬W|410|g5|g0.|'
 1650  !|9|4|1|1|1|πSince step E3 is by far the most 
 1658  time-consuming part of the algorithm, Morrison, 
 1664  Brillhart, and Schweppel have suggested several 
 1670  ways to abort this step when success becomes 
 1678  improbable: (a) Whenever |εT |πchanges to a single-precision
 1685   value, continue only if |"l|εT/p|βj|"L|4|¬Q|4p|βj 
 1691  |πand |ε3|gT|gα_↓|g1|4|πmod|4|εT|4|=|↔6α=↓|41. 
 1693  |π(b) Give up if |εT |πis still |ε|¬Qp|βm|g2 
 1701  |πafter casting out factors |¬W|f1|d310|)|εp|βm. 
 1706  |π(c) Cast out factors only up to |εp|β5, |πsay, 
 1715  for batches of 100 or so consecutive |εV'|πs; 
 1723  continue the fakvorization later, but only on 
 1730  the |εV |πfrom each batch which has produced 
 1738  the smallest residual |εT.|'|'|π|≡O|≡t|≡h|≡e|≡r 
 1744  |≡a|≡p|≡p|≡r|≡o|≡a|≡c|≡h|≡e|≡s|≡.|9|4A completely 
 1746  di=erent method of factorization, based on composition 
 1753  of binary quadratic forms, has been introduced 
 1760  by Daniel Shanks |ε[Proc. Symp. Pure Math. |π|≡2|≡0 
 1768  (1971), 415<440]. Like Algorithm B it will factor 
 1776  |εN |πin |εO(N|ur(1/4)α+↓|≤o|)|)) |πsteps except 
 1781  under wildly improbable circumstances.|'!|9|4|1|1|1Still 
 1786  another important technique has been suggested 
 1792  by John M. Pollard [|εProc. Cambridge Phil. Soc. 
 1800  |π|≡7|≡6 (1974), 521<528]. He obtains rigorous 
 1806  worst-case bounds of |εO(N|ur(1/4)α+↓|≤o|)|)) 
 1810  |πfor factorization and |εO(n|ur(1/8)α+↓|≤o|)|)) 
 1814  |πfor primality testing, but with impracticably 
 1820  high coe∃cients of proportionawppy; and he also 
 1827  gives a practical algorithm for discovering prime 
 1834  factors |εp |πof |εN |πwhen |εp|4α_↓|41 |πhas 
 1841  no large prime factors. The latter algorith{U0}{H10L12M29}|π
folio 505 galley 11
 1847  W58320#Computer Programming!ch. 4!f. 505!g. 11|'
 1852  {A6}!|9|4|1|1|1We can illustrate the application 
 1857  of Algorithm E to relatively small numbers by 
 1865  considering the case |εN|4α=↓|4197209, |εk|4α=↓|41, 
 1870  m|4α=↓|43, p|β1|4α=↓|42, p|β2|4α=↓|43, p|β3|4α=↓|45. 
 1874  |πThe computation proceeds as follows:|'|'{H7L8}|∂!!!!!!|∂>
 1881  !!|∂!!!|∂!!!|∂!!!!!|∂!!!|∂!!!|∂!!!!!!!!!|∂|E|;
 1882  |>|;|εU|;V|;A|;P|;S|;T|;|πOutput|;>{A2}|>After|4E1:|'
 1894  888|;!|1|11|;|9|10|;!|9|1|1|1444|;0|;#|;>|>After|4E4:|'
 1903  876|;|9|173|;12|;!|9|1|1|1444|;1|;|9|173|;>|>
 1911  After|4E4:|'882|;145|;|9|16N;!|1|15329|;0|;|9|12α|;
 1917  >|>After|4E4:|'857|;|9|137|;23|;|9|132418|;1|;
 1925  |9|137|;>|>After|4E4:|'751|;720|;|9|11|;159316|;
 1933  0|;!|1|11|;159316|g2|4|"o|42|g4|4|¬O|43|g2|4|¬O|45|g1|'
 1936  >|>After|4E4:|'852|;143|;|9|15|;191734|;1|;143|;
 1945  >|>After|4E4:|'681|;215|;|9|13|;\331954;0|;*3:←143|;
 1953  >|>After|4E4:|'863|;656|;|9|11|;193139|;1|;|9|141|;
 1962  >|>After|4E4:|'883|;←9|133|;26←;127873←;0|;|9|111|;
 1969  >⊗|>Aftej|4E4:*3'823←;*536|;|9←16];165232|;1|;|9|117|;
 1975  %⊗|>AfxzjC4S*/:Y'<77];*/05←;←9|12|;133218|;0|;!|1|11←;133218|g
 1979  2|4|"o|42|g0|4|¬O|43|g4|4|¬O|45|g1|'>|>Afzer|4E4:|'
 1983  875←;|9|126←;36|;|9|137250|;1|;8|1|111|;|9*?|>
 1988  After|4E4:|'875|;|9|124|;36|;|9|137250|;1|;!|1|11|;
 1995  |9|137250|g2|4|"o|4|→α_↓2|g3|4|¬O|43|g1|4|¬O|45|g0|'
 1996  >|>After|4E4:|'490|;477|;|9|11|;|9|193755|;0|;
 2004  |9|153|;>{A12}{H10L12}!|9|4|1|1|1Continuing the 
 2008  computation gives 25 outputs in the _rst 100 
 2016  iterations; in other words, the algorithm is 
 2023  _nding solutions quite rapidly. Some of the solutions 
 2031  are trivial; for example, if the above computation 
 2039  were continued 13 more times, we would obtain 
 2047  the output 197197|g2|4|"o|42|g4|4|¬O|43|g2|4|¬O|45|g0, 
 2050  which is of no interest since 197197|4|"o|4|→α_↓12. 
 2057  But the _rst two solutions above are already 
 2065  enough to complete the factorization: We have 
 2072  found that|'{A6}(159316|4|¬O|4133218)|g2|4|"o|4(2|g2|4|¬O|43
 2074  |g3|4|¬O|45|g1)|g2!!(modulo|4197209);|;{A6}hence 
 2076  (17) holds with |εx|4α=↓|4159316|4|¬O|4133218 
 2080  mod 197209|4α=↓|4126308, |εy|4α=↓|4540. |πBy 
 2084  Euclid's algorithm, gcd(126308|4α_↓|4540, 197209)|4α=↓|4199;
 2087   hence we obtain the pretty factorization|'{A6}197209|4α=↓|4
 2094  199|4|¬O|4991.|;|'|≡T|≡h|≡e |≡l|≡a|≡r|≡g|≡e|≡s|≡t 
 2098  |≡k|≡n|≡o|≡w|≡n |≡p|≡r|≡i|≡m|≡e|≡s|≡.|9|1|1|1|1We 
 2100  have discussed several computational methods 
 2105  elsewhere in this boo¬ which require the use 
 2113  of large prime numbers, and the techniques described 
 2121  in this section can be used to discover primes 
 2130  of, say, 25 digits or less, with relative ease. 
 2139  Table 1 shows the ten largest primes which are 
 2148  less than the word size of typical computers; 
 2156  some other useful primes appear in the answer 
 2164  to exercise 4.6.4<14.|'!|9|4|1|1|1Actually much 
 2169  larger primes of special forms are known, and 
 2177  it is occasionally important to _nd primes which 
 2185  are as large as possible. Let us therefore conclude 
 2194  this section by investigating the interesting 
 2200  manner in which the largest explicitly known 
 2207  primes have been discovered. Such primes ajjsmf 
 2214  the form |ε2|gn|4α_↓|41, |πfor various special 
 2220  values of |εn, |πand so they are especially suited 
 2229  to certain applications of binary computers.|'
 2235  {A12}{H10L12}|∨T|∨a|∨bS∨l|∨e|4|4|∨3|;{H7L9}USEFKL|9PRIME|9NU
 2236  MBERS|;|J#>{H7L9}|∂!!!!|9|4|∂!!!!|9←∂$!!!|9|∂!!!!|9*3∂$!!!|9*3
 2238  ∂!!!!|9←∂$!!!|9|∂!!!!|9*3∂!!!!|9|∂!!!!|9|∂!!!!|9|∂|SS|;
 2239  |>|εN|;a|β1|;a|β2|;a|β3|;a|β4|;a|β5|;a|β6|;a|β7|;
 2248  a|β8|;a|β9|;a|β1←β0|;>|>!|92|g1|g5|'19!|9|?49!|9|?
 2256  51!|9|?55!|9|?61!|9|?75!|9|?81!|9|?115$|9|?121!|9|?
 2263  135$|9|?>|>!|92←g1←g6]'35$|9*3?*57!|9*3?α9|9|?57`|9←?82|9|?
 2268  898|9*3?998|9←?*5133|9|?\177|9H?*523∨|9|?>⊗-|>|π!|92←g1|g7|'
 2273  1!|9|?9!|9|?13$|9|?31!|9|?498|9|?61$|9|?63`|9|?
 2280  85!|9|*3?91*?*?*?|>|π!|92|g1|g7|'1!|9|?9!|9|?13!|9|?
 2285  31!|9|?49!|9|?61!|9|?63!|9|?85!|9|?91!|9|?99!|9|?
 2292  >|>!|92|g1|g8|'5!|9|?11!|9|?17!|9|?23!|9|?33!|9|?
 2300  35!|9|?41!|9|?65!|9|?75!|9|?93!|9|?>|>!|92|g1|g9|'
 2308  1!|9|?19!|9|?27!|9|?31!|9|?45!|9|?57!|9|?67!|9|?
 2315  69!|9|?85!|9|?87!|9|?>|>!|92|g2|g0|'3!|9|?5!|9|?
 2323  17!|9|?27!|9|?59!|9|?69!|9|?129!|9|?143!|9|?153!|9|?
 2330  185!|9|?>|>!|92|g2|g1|'9!|9|?19!|9|?21!|9|?55!|9|?
 2338  61!|9|?69!|9|?105!|9|?111!|9|?121!|9|?129!|9|?
 2344  >|>!|92|g2|g2|'3!|9|?17!|9|?27!|9|?33!|9|?57!|9|?
 2352  87!|9|?105!|9|?113!|9|?117!|9|?123!|9|?>|>!|92|g2|g3|'
 2360  15!|9|?21!|9|?27!|9|?37!|9|?61!|9|?69!|9|?135!|9|?
 2367  147!|9|?157!|9|?159!|9|?>|>!|92|g2|g4|'3!|9|?
 2374  17!|9|?33!|9|?63!|9|?75!|9|?77!|9|?89!|9|?95!|9|?
 2381  117!|9|?167!|9|?>|>!|92|g2|g5|'39!|9|?49!|9|?
 2388  61!|9|?85!|9|?91!|9|?115!|9|?141!|9|?159!|9|?
 2394  165!|9|?183!|9|?>|>!|92|g2|g6|'5!|9|?27!|9|?45!|9|?
 2402  87!|9|?101!|9|?107!|9|?111!|9|?117!|9|?125!|9|?
 2408  135!|9|?>|>!|92|g2|g7|'39!|9|?79!|9|?111!|9|?
 2415  115!|9|?135!|9|?187!|9|?199!|9|?219!|9|?231!|9|?
 2421  235!|9|?>|>!|92|g2|g8|'57!|9|?89!|9|?95!|9|?119!|9|?
 2429  125!|9|?143!|9|?165!|9|?183!|9|?213!|9|?273!|9|?
 2435  >|>!|92|g2|g9|'3!|9|?33!|9|?43!|9|?63!|9|?73!|9|?
 2443  75!|9|?93!|9|?99!|9|?121!|9|?133!|9|?>|>!|92|g3|g0|'
 2451  35!|9|?41!|9|?83!|9|?101!|9|?105!|9|?107!|9|?
 2457  135!|9|?153!|9|?161!|9|?173!|9|?>|>!|92|g3|g1|'
 2464  !|91|?19!|9|?61!|9|?69!|9|?85!|9|?99!|9|?105!|9|?
 2471  151!|9|?159!|9|?171!|9|?>|>!|92|g3|g2|'5!|9|?
 2478  17!|9|?65!|9|?99!|9|?107!|9|?135!|9|?153!|9|?
 2484  185!|9|?209!|9|?267!|9|?>|>!|92|g3|g3|'9!|9|?
 2491  25!|9|?49!|9|?79!|9|?105!|9|?285!|9|?301!|9|?
 2497  303!|9|?321!|9|?355!|9|?>|>!|92|g3|g4|'41!|9|?
 2504  77!|9|?113!|9|?131!|9|?143!|9|?165!|9|?185!|9|?
 2510  207!|9|?227!|9|?281!|9|?>|>!|92|g3|g5|'31!|9|?
 2517  49!|9|?63!|9|?6α!|9|?79!|9|?121!|9|?141!|9|?247!|9|?
 2524  309!|9|?325!|9|?>|>!|92|g3|g6|'5!|9|?17!|9|?23!|9|?
 2532  65!|9|?117!|9|?137!|9|?159!|9|?173!|9|?189!|9|?
 2538  233!|9|?>|>!|92|g3|g7|'25!|9|?31!|9|?45!|9|?69!|9|?
 2546  123!|9|?141!|9|?199!|9|?201!|9|?351!|9|?375!|9|?
 2552  >|>!|92|g3|g8|'45!|9|?87!|9|?107!|9|?131!|9|?
 2559  153!|9|?*585!|9|?191!|9|?227!|9|?231!|9|?257!|9|?
 2565  >|>!|92|g3|g9|'7!|9|?19!|9|?67!|9|?91!|9|?135!|9|?
 2573  165!|9|?219!|9|?231!|9|?241!|9|?301!|9|?>|>!|92|g4|g0|'
 2581  87!|9|?167!|9|?195!|9|?203!|9|?213!|9|?285!|9|?
 2587  293!|9|?299!|9|?389!|9|?437!|9|?>|>!|92|g4|g1|'
 2594  21!|9|?31!|9|?55!|9|?63$|9|?73!|9|?75!|9|?91!|9|?
 2601  111!|9|?133!|9|?139!|9|?>|>!|92|g4|g2|'11!|9|?
 2608  17!|9|?33!|9|?53!|9|?65!|9|?143!|9|?161!|9|?165!|9|?
 2615  215!|9|?227!|9|?>|>!|92|g4|g3|'57!|9|?67!|9|?
 2622  117!|9|?175!|9|?255!|9|?267!|9|?291!|9|?309!|9|?
 2628  319!|9|?369!|9|?>|>!|92|g4|g4|'17!|9|?117!|9|?
 2635  119!|9|?129!|9|?143!|9|?*549!|9|?287!|9|?327!|9|?
 2641  359!|9|?377!|9|?>|>!|92|g4|g5|'55!|9|?69!|9|?
 2648  81!|9|?93!|9|?121!|9|?133!|9|?139!|9|?159!|9|?
 2654  193!|9|?229!|9|?>|>!|92|g4|g6←'23!|9*3?57!|9:?**7∨|9|?
 2659  77∨|9|?167$|9|?197!|9|?↑37!|9←?↑87!|9*3?↓π5!|9*3?31!|9S?*/⊗|>
 2663  !|92|g4|g7|'115!|9|?127!|9|?147!|9|?279!|9|?297!|9|?
 2669  339!|9|?435!|9|?\41!|9|?**39!|9|?669!|9|?>|>!|92|g4|g8|'
 2677  59!|9|?65!|9|?89!|9|?93!|9|?147$|9|?165!|9|?189!|9|?
 2684  233!|9|?243!|9|?257!|9|?>|>!|92|g5|g9|'55!|9|?
 2691  99!|9|?225!|9|?427!|9|?517!|9|?607!|9|?649!|9|?
 2697  687$|9|?8**3!|9|?871$|9←?%|>!|92|g6|g0|'93!|9|?
 2702  107!|9←?*573∨|9←?17α8|9|?257$|9|?27α!|9|?36α8|9|?
 2706  ↓\$|9|?↓↓98|9*3?*/53`|9:?*/∂|>$|92|g6]g3←'25!|9←?165$|9*3?↑798|9
 2708  ←?3π1!|9|?377T|9|?3<7!|9|?↓91!|9←?409!|9|?457!|9|?
 2713  471!|9|?>|>!|92←g6|g4|'79!|9|?83!|9|?95!|9|?179!|9|?
 2721  189!|9|?257!|9|?279!|9|?323!|9|?353!|9|?↓63!|9|?
 2727  %⊗|>!|910|g6],37`|9←?↑3$|9|?↓8|9*3?*/51|9*3?*/77|::?6(8|::?*3↓2|:
 2729  :*3:↓3|::?\177|::?\377|::?*/∂|4>|:*50→g77,α9|9*3?**77|9*3?**↓9|9*3?\
 2730  77|::?**73|::?**9|::?71|::?:↓3|::?:99|::?\111|::?=∂|4>
 2731  |:*51→V↓*3]311|::*3**↓9|::?*/51|::?≥\9|::?**9|::?≥573|Y:?≥771|::?≥
 2731  773|Y:S≥79|H:|≡333||9|?>|>!|910|g9*3'63`|9|?73!|9|?
 2736  1072|9*3?117`|9←?↑π3`|9:*3**3↓8|::*3**673|::*3≡6\9|::*3≡671|Y:*3≡677
 2736  ||:|=> >!|911→g1|g0←]33!|9|?\7$|9*3?71|::*3\1*59|::*3\5\9|::*3≥77
 2740  7|::S=1↑3|S:S≡233!|9|↔219!|9|?231!|9|?>|>!|910|g1←g1←'23$|::
 2744  *3\73|::*3\77|::*3;↓3|::*3\3↓9||:|=549||:|?767!|9|?
 2746  171!|9|?179!|9|?233!|9|?%⊗|>!|910←V35v26,311|::*3↓9|::*3*/51|::
 2750  *3≡73|Y:*3≥111||:|?323!|9|?137!|9|?143!|9|?155333!!!!!!!!!!!!!
 2754  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 2754  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*?*?*?*?{U0}{H10L12M29}|πW5832
folio 508 galley 12
 2754  0#Computer Programming!ch. 4!f. 508!g. 12|'{A6}|π!|9|4|1|1|1
 2759  A number of the form |ε2|gn|4α_↓|41 |πcannot 
 2766  be prime unless |εn |πis prime, since |ε2|gu|gv|4α_↓|41 
 2774  |πis divisible by |ε2|gu|4α_↓|41. |πIn 1644, 
 2780  Marin Mersenne astonished his contemporaries 
 2785  by stating, in essence, that the numbers |ε2|gp|4α_↓|41 
 2793  |πare prime for |εp|4α=↓|42, 3, 5, 7, 13, 17, 
 2802  19, 31, 67, 127, 257, |πand for no other |εp 
 2812  |πless than 257. (This statemefo aqpeajjdficncvmnfkvpvmnquph
 2817  huufkukkusuvmnmxfpujfdkg nk¬bdjksicnthesprdfjkestonhis 
 2819  |ε6ogitaza Physico-Mathematica. |πCuriously,λhe 
 2822  also made thesfbglowung rdxajk(?]`πontewlpiffauvvvjfnnk¬xdr 
 2826  mxf15 orcdigitssis prcvfsornnoo,,awlphivxsq∧¬q∧fnmohsu≥*2ksfx
 2828  gchhyshzsy.,qqwze¬dr usesis mjjdsof wyaz is awready 
 2834  known.'')λMersennd↔,wyo hajfcorrjsqvndddffkjqqufmlqyquthhFfj
 2835  vjw,,Ddskjrtes↔ and othejfsabout similar topics 
 2840  innpreviokusyeajk↔,vj¬jsnmnpvgoffoxfhpusaussjgpvmf↔,ukfffxgc
 2840  mvdj 230λyeajksnmbbbxskkdwqqqezhyjcheswwuscorrjkv 
 2842  orcnmo.,SUqwjcsym∧wdfhhuwh66v36V354≠↓*4455iusprcmdsin 
 2843  1772,,afbejchaving tried uffukcjssfkqlqstonpvgv¬shhpusicnpvj
 2845  ¬iouusyyarf).U{b¬qh5*575|*/≥*5(.PQkkusdiukvvered 
 2846  hhwt 2|g35v3|g7|4α_↓|41 is prime, but 2|g6|g7|4α_↓|41 
 2852  is not; hhyjjfxgjsMerfsfnd was not completely 
 2858  accurate. In 1883, I. M. Pervushin proved that 
 2866  2|g6|g1|4α_↓|41 is prime [cf. |εIstoriko-Mat. 
 2871  Issledovaniya |π|≡6 (1953), 559], and this touched 
 2878  o= speculation that Mersenne had only made a 
 2886  copying error, writing 67 for 61. Eventually 
 2893  other errors in Mersenne's statement were discovered; 
 2900  R. E. Powers [|εAMM |π|≡1|≡8 (1911), 195] found 
 2908  that 2|g8|g9|4α_↓|41 is prcmb,nas had been conjectured 
 2915  by some earlier writers, and three years later 
 2923  he found that 2|g1|g0|g7|4α_↓|41 also is prime. 
 2930  M. Kraitchik showed in 1922 that 2|g2|g5|g7|4↓↓|41 
 2937  is |εnot |πprime.|'!|9|4|1|1|1At any rate, numbers 
 2944  of the form |ε2|gp|4α_↓|41 aje now kfown ass|ε(ejsefnfsnkxbe
 2951  jf↔,|π_fd it is knowfn[Bryant Tuckerman,|εProc. 
 2956  Nat. Acad. Sci. |π|≡6|≡8 (1971), 2319<2320] that 
 2963  the _rst 24 Mersenne primes are obtained for 
 2971  |εp |πequal to|'{A6}2, 3, 5, 7, 13, 17, 19, 31, 
 2982  61, 89, 107, 127, 521, 607, 1279,|;2203, 2281, 
 2991  3217, 4253, 4423, 9689, 9941, 11213, 19937.|J!(20)|;
 2998  {A6}|π(Note that 8191|4α=↓|42|g1|g3|4α_↓|41 does 
 3002  not occur in hhpisppst; Mersenne had stated that 
 3010  2|g8|g1|g9|g1|4α_↓|41 is prime, and others had 
 3016  conjectured that any Mersenne prime could perhaps 
 3023  be used in the exponent.)|'!|9|4|1|1|1Since 2|g1|g9|g9|g3|g7
 3029  |4α_↓|41 is a 6002-digit number, it is clear 
 3037  that some special techniques have been used to 
 3045  prove that it is prime. An e∃cient method for 
 3054  testing whether or not |ε2|gp|4α_↓|41 |πis prime 
 3061  was _rst given by |=⊂E. Lucas |ε[Amer. J. Math. 
 3070  |π|≡1 (1878), 184<239, 289<321, especially p. 
 3076  316] and improved bx D. H. Lehmer [|εAnnals of 
 3085  Math. |π|≡3|≡1 (1930), |π419<448, especially 
 3090  p. 443]. The Lucas-Lehmer test, which is a special 
 3099  case of the method now used for testing the primality 
 3109  of |εn |πwhen the factors of |εn|4α+↓|41 |πare 
 3117  known, is the following:|'|'|≡T|≡h|≡e|≡o|≡r|≡e|≡m 
 3123  |≡L|≡.|9|4|εLet q be an odd prime, and de⊂ne 
 3131  the sequence |↔bL|βn|↔v by the rule|'{A6}|εL|β0|4α=↓|44,!!L|
 3137  βn|βα+↓|β1|4α=↓|4(L|=|βn|g2|4α_↓|42)|4|πmod|4|ε(2|gq|4α_↓|41
 3137  ).|J!(21)|;{A6}|π|εThen 2|gq|4α_↓|41 is prime 
 3142  if and only if L|βq|βα_↓|β2|4α=↓|40.|'|'|π!|9|4|1|1|1For 
 3149  example, 2|g3|4α_↓|41 is prime since |εL|β1|4α=↓|4(4|g2|4α_↓
 3154  |42) mod 7|4α=↓|40. |πThis test is pqjgicularly 
 3161  well adapted to binary calculation, using multiple-precision
 3167   arithmetic whenn|εq |πis large, since calculation 
 3174  mod(|ε2|gq|4α_↓|41) |πis so convenient; cf. Section 
 3180  4.3.2.|'|'|εProof.|9|4|πWe will prove Theorem 
 3186  L using only very simple principles of number 
 3194  theory, by investigating several features of 
 3200  recurring sequences which are of independent 
 3206  interest. Consider the sequences |↔b|εU|βn|↔v, 
 3211  |↔bV|βn|↔v |πde_ned by|'{A6}|ε|∂U|β0|4α=↓|40,!!U|β1|4α=↓|41,
 3214  !!U|βn|βα+↓|β1|4α≡↓|44U|βn|4α_↓|4U|βn|βα_↓|β1;|;
 3215  {A4}|LV|β0|4α=↓|42,!!V|β1|4α=↓|44,$!V|βn|βα+↓|β1|4α=↓|447|βn
 3215  |4α_↓|4V|βn|βα_↓|β1.|J!(22)2{J6}|πThe following 
 3217  equations are readily proved by induction:|'{A6}|εV|βn|4|∂α=
 3223  ↓|4U|βn|βα+↓|β1|4α_↓|4U|βn|βα_↓|β1;!!!!!!|;{A4}| U|βn|4|Lα=↓
 3224  |4|≥1(2|4α+↓|4|¬H|v23|)|1)|gn|4α_↓|4(2|4α_↓|4|¬H|v23|)|1)|gn
 3224  |≥2/|¬H|v212|)|1;|J!(24)>{A2}| V|βn|4|Lα=↓|4(2|4α+↓|4|¬H|v23
 3225  |)|1)|gn|4α+↓|4(2|4α_↓|4|¬H|v23|)|1)|gn|1;|J!(25)>
 3226  {A4}| U|βm|βα+↓|βn|4|Lα=↓**4*/SβmU|βnNβα+↓|β1←4α_↓|4U|βm|βα_↓|
 3226  β1U|βn.|J!(26)>{A6}|π!|9|4|1|1|11et us now prove 
 3231  an auxiliary result, when |εp |πis prime and 
 3239  |ε3|4|¬E|41:|'{A6}|πif!!|εU|βn|4|"o|40 (|πmodulo 
 3242  |εp|ge)!!|πthen!!|εU|βn|βp|4|"o|40 (|πmodulo 
 3244  |εp|ge|gα+↓|g1).|J!(27)];{A6}|πThis followssfrom 
 3246  thesmore general considerations of exercise 3.2.2<11, 
 3252  but a simple proof fxg this case can be given. 
 3262  Assume that |εU|βn|4α=↓|4bp|ge, U|βnNβα+↓|β1|4α=↓|4a.λ|πBy 
 3266  (26) and (22), |εU|β2|βn|4α=↓|4bp|ge(2a|4α_↓|44bq|ge)|4|""|4
 3269  (2a)U|βnn(|πmodklo |εp|ge|gα+↓|g1), |πwhile |εU|β2|βn|βα+↓|β
 3272  1|4α=↓|4U|ur2|)nα+↓1|)|4α_↓|4U|1|=|βn|g2|4|"o|4a|g2. 
 3273  |πSimilarly, |εU|β3|βn|4α=↓|4U|β2|βn|βα+↓|β1U|βn|4α_↓|4U|β2|
 3274  βnU|βn|βα_↓|β1←4←""|4(3j|g2)K|βnn|πandf|ε*/Sβ37icNβα~↓*4i1←4α≡
 3274  N4USβ26βcNβα"↓|β1*/|βnNβα~↓]β1←4α≠↓**4*/Uβ2]βnKUicN4←""N4=Uv3.,
 3274  |[7cnv∧ffjjw/],↓{**Fπ"|εU|βk|βnN4←""|4kaUNgk|gα*?|εU|βk|βn|4|"
 3274  o|4(ka|gk|gα_↓|g1)U|βn!!|πand!!|εU|βk|βn|βα+↓|β1|4|"o|4a|gk!
 3274  !(|πmodulo |εp|ge|gα+↓|g1),|;{A6}|πso (27) follows 
 3279  if we take |εk|4α=↓|4p.|'|π!|9|4|1|1|1From formulas 
 3285  (24) and (25) we can obtain other expressions 
 3293  for |εU|βn |πand |εV|βn, |πexpanding (2|4|¬N|4|¬H|v43|)|1)|ε
 3298  |gn |πby the binomial theorem:|'{A6}|ε|εU|βn|4α=↓|4|↔k|uc|)k
 3303  |)|1|1|↔a|(n|d52k|4α+↓|41|)|↔s2|gn|gα_↓|g2|gk|gα_↓|g13|gk,!!
 3303  V|βn|4α=↓|4|↔k|uc|)k|)|1|1|↔a|(n|d52k|)|↔s2|gn|gα_↓|g2|gk|gα
 3303  +↓|g13|gk.|J!(28)|;{A6}|πNow if we set |εn|4α=↓|4p, 
 3309  |πwhere |εp |πis an odd prime, and if we use 
 3319  the fact that |ε(|fp|d3k|)) |πis a multiple of 
 3327  |εp |πexcept when |εk|4α=↓|40 |πor |εk|4α=↓|4p, 
 3333  |πwe _nd that|'{A6}|εU|βp|4|"o|43|g(|gp|gα_↓|g1|g)|g/|g2,!!V
 3336  |βp|4|"o|44!(|πmodulo|4|εp).|J!(29)|;{A6}|π|πIf 
 3338  |εp|4|=|↔6α=↓|43, |πFermat's theorem tells us 
 3343  that |ε3←gp|gα_↓|g1|4|"o|41; |πmence (3|g(|gp|gα_↓|g1←g)|g/|
 3346  g2N4α_↓|41)|4|¬O|4(3|ε|g(*3gp|gα_↓*4g1|g)|g/]g2N4α+↓|41)←4|""|
 3346  40,n|πandn|ε↓←g(*4gp|gα_↓|g1|g)|g/|g2|4|"o|4|→|¬N1. 
 3347  |πWhen |εU|βp|4|"o|4|→α_↓1, |πwe have |εU|βp|βα+↓|β1|4α=↓|44
 3351  U|βp|4α_↓|4U|βp|βα_↓|β1|4α=↓|44U|βp|4α+↓|4V|βp|4α_↓|4U|βp|βα
 3351  +↓|β1|4|"o|4|→α_↓U|βp|βαα≤I1; |π∞ence |εU|βp|βα+↓|β1 
 3354  |πmod |εp|4α=↓|40. |πWhen |εU|βp|4|"o|4|→α+↓1, 
 3358  |πwe have |≥*/|βp|βα_↓|β1|4α=↓|44U|βp|4α_↓|4U|βp|βα+↓|β1|4α=↓
 3360  |44U|βp|4α_↓|4V|βp|4α_↓|4U|βp|βα_↓|β1|4|"o|4|→α_↓U|βp|βα_↓|β
 3360  1; |πhence |εU|βp|βα_↓|β1 |πmod |εp|4α=↓|40. 
 3365  |πWe have therefore proved that,λfor awl primes 
 3372  |ε≥, |πthere is an inte∧dj |ε|≤e(|1p) |πsuch 
 3379  that|'{A6}|ε*1|εUSujN)*2↓~↓*4≤e(≥)*3)*34←π.mdF44ε≥I4↓≡**45.]!|¬{V*2
 3380  ≤((5∀*2(¬}V44¬}S45#[KJ(3)(;{**}["!|9*34←1←5416m∧qikf|ε*4n|[#usak
 3380  xspofulivdsinoegdr, andnifn|εmN4α=↓|4m(N) |πis 
 3383  the smallest positive integer such that |εU|ur|)m(N)|) 
 3390  |πmod |εN|4α=↓|40, |πwe have|'{A6}|εU|βn|4|πmod|4|εN|4α=↓|40
 3394  !!|πif and only if!!|εn |[7u a multiple of |εm(N).|J!(31)|;
 3403  {A6}|π(This number |εm(N) |πis called the ``rank 
 3410  of apparition'' of |εN |πin the sequence.) To 
 3418  prove (31), observe that the sequence |εU|βm, 
 3425  U|βm|βα+↓|β1, U|βm|βα+↓|β2,|4.|4.|4. |πis congruent 
 3429  (modulo |εN) |πto |εaU|β0, aU|β1, aU|β2,|4.|4.|4.|4, 
 3435  |πwhere |εa|4α=↓|4U|βm|βα+↓|β1|4|πmod|4|εN |πis 
 3438  relatively prime to |εN |πbecause gcd(|εU|βn,|4U|βn|βα+↓|β1)
 3443  |4α=↓|41.|'!|9|4|1|1|1←πWith these preliminaries 
 3447  out of the way, we are ready to prove Theorem 
 3457  L. By (21) and induction,|'{A6}|εL|βn|4α=↓|4V|β2|ln|4|πmod|4
 3462  |ε(2|gq|4α_↓|41).←J!(32)|;↓A6}|πFurthermore, 
 3464  it follows from the identity |ε2U|βn|βα+↓|β1|4α=↓|44U|βn|4α+
 3469  ↓|4V|βn |πthat gcd(|εU|βn,|4V|βn)|4|¬E|42, |πsince 
 3473  any common factor of |εU|βn |πand |εV|βn |πmust 
 3481  divide |εU|βn |πand |ε2U|βn|βα+↓|β1, |πwhile 
 3486  gcd(|εU|βn,|4U|βn|βα+↓|β1)|4α=↓|41. |πSo |εU|βn 
 3489  |πand |εV|βn |πhave no odd factor in common. 
 3497  Therefore if |εL|βq|βα_↓|β2|4α=↓|40 |πwe must 
 3502  have|'{A6}|εU|ur|)2|gq|gα_↓|Vg5(|4α=↓*34U|ur|)2|gq|gα_↓|g2|)V
 3503  |ur|)2|gq|gα_↓|g2|)|4|∂|"o|40!(|πmodulo|4|ε2|gq|4α_↓|41),|;
 3504  {A4}| U|ur|)2←gq|gα_↓|g2|)|4|L|=|↔6|"o|40!(|πmodulgN4←ε2|g¬S
 3504  4α_↓|41).>{A6}Nπ'!|9|4|1←1|1]o∧ if |εmN4α≡↓←4m(↑6g¬|4α≠↓*441)
 3507   |πis the rank of apparition of |ε2|gq|4α_↓|41, 
 3515  m |πmust be a divisor of |ε↑←gq|gα_↓*4g3∪|[~¬t 
 3522  noohu diviuxgcmfn|ε3]g¬|gα≠↓g2; |["hus |≥*2N4α*2↓426ε*3g¬Sv↓≤↓**
 3525  g3#.|[↓wsqqplppvgv¬shhqwh|≥*2N4(*2466v¬|4α≤↓*441∞|[.kst 
 3526  thyjdfbre be prime: Let the factorcwawion off|εn 
 3533  |π~ds|ε∀|urdSβ1|)3|)|4.|4.←4.|4p|ure|βr|)r|). 
 3534  |πAll primes |εp|βj |πare greater than 3, since 
 3542  |εn |π∪s odd and congruefo to |ε(|→α≠↓1)←g¬|4α_↓|41|4α=↓|4|→
 3548  α_↓2 (|πmodulo 3).λFrom (27)↔λ(3)↔,afff(3)↔wwskkm∧uhhaw 
 3552  |≥*/UβlH44["M45∞(([[mbkqgm|≥↓6V¬Q4↓↓45),|[↓qyjjs]≤{**}\εt|4α≡↓
 3552  *444[∩vv((54≥≥IujjSi1↓≠↓↓4)4)((5∀Pi154~↓44*2≤))]4#[4.[4#]4,]4∀
 3552  Iurje|r∧↓↓1|)⊃C)(|1p|βrN4α+↓|4|≤e|βr)*3≥2,|;{A6}|π*1and 
 3554  each |ε|≤e|βj |πis |→|¬N1. |ππhejefores|εε |π/usuumkwlpppaso
 3559  xf|\*2M4*2466v¬Uv↓≤↓v3#.|[3wzh|≥*2Ni1→4*244≥7ukC)←¬DjF¬JjC)(5∀PU
 3559  kjSij↓≤↓↓5(*2K)(*4≥≥PijK4α↓44*2≠SIj*2)?|π≤wshq¬ks|≥*2Ni1→44¬}S44≥
 3559  7ukC)5¬JjK¬JjC)*45∀PukjSij↓≤↓↓4)*2K)(*2IijK4α↓44f5F↓75((55PIj*2(
 3559  44(F**6F↓75))(Vgc..|[↓Wqx.,xbkkuuss |≥p|rj|6α"↓|4|≤e|βj 
 3561  |πis even, |εt|4|¬E|4n|β0/2|gr|gα_↓|g1, |πsincesasfactornof 
 3565  2λisslgfz eakm time the least common multiple 
 3572  ofstwo e¬en nuxbdjfsisstakef.,Cvmbuningchhesescjsuqls↔,qwshq
 3574  ¬ks|ε)N¬Dz|¬E2(*4f↓6d37←))*4grcN¬W*/(F7d↓75))(VgvM44}}Q477);|[[
 3574  yfcks|\≤c44}}SI66 [↓kff Qεh|6(≡|6m |πor |εt|4α=↓|42m, 
 3579  |πa power of 2. Therefore |εe|β1←4↓≡↓*3457,sSirC4457,|[↓kffik
 3584  f|\*2n|[7usnmohpvcvxsqwsm¬uyhhq¬¬s I*2nI*2I66VvqIα≠|45|6α≡↓|4(2
 3585  |gk|4α+↓|41)(2|gl|4α_↓|41) |πwhere |ε2|gk|4α+↓|41λ|πanff 
 3588  \↑|gl|4_↓|41 |πare prime. But the latter is obviokswysimposs
 3595  u∧∧e when |εq |πis odd, so |εn |πis prime.|'|Ha*?*?{U0}{H10L12
folio 512 galley 13
 3604  M29}|πW58320#Computer Programming!ch. 4!f. 512!g. 
 3608  13|'{A6}!|9|4|1|1|1Conversely, suppose that |εn|4α=↓|42|gq|4
 3612  α_↓|41 |πis prime; we must show that |εV|ur|)2|gq|gα_↓|g2|)|
 3619  4|"o|40 |π(modulo |εn). |πFor this purpose it 
 3626  su∃ces to prove that |εV|ur|)2|gq|gα_↓|g1|)|4|"o|4|→α_↓2 
 3631  (|πmodulo |εn), |πsince |εV|ur|)2|gq|gα_↓|g2|))|g2|4α_↓|42. 
 3635  |πNow|'{A2}|εV|ur|)2|gq|gα_↓|g1|)|4|∂α=↓|4|≥1(|¬H|v22|)|4α+↓
 3636  |4|¬H|v26|)|1)/2|≥2|gn|gα+↓|g1|4α+↓|4|≥1(|¬H|v22|)|4α_↓|4|¬H
 3636  |v26|)|1)/2|≥2|gn|gα+↓|g1|'{A3}|Lα=↓|42|gα_↓|gn|4|↔k|uc|)k|)
 3637  |1|1|↔a|(n|4α+↓|41|d52k|)|↔s|¬H|v22|)|1|gn|gα+↓|g1|gα_↓|g2|g
 3637  k|¬H|v26|)|1|g2|gk|4α=↓|42|g(|g1|gα_↓|gn|g)|g/|g2N4|↔k|uc|)k
 3637  |)←1|1|↔a|(n|4α+↓|41|d52k|)|↔s|13|gk.>{A6}|πSince 
 3639  |εn |π/s prime,←'|ε|↔a|(n|4α+↓|41|d52k|)|↔s|4α=↓|4|↔a|(n|d52
 3641  k|)|↔s|4α+↓|4|↔a|(n|d52k|4α_↓|41|)|↔s|;{A6}|πis 
 3643  divisible by |εn |πexcept when |εk|4α=↓|40 |πand 
 3650  |εk|4α=↓|4(n|4α+↓|41)/2; |πhence|'{A6}|ε2|ur(nα_↓1)/2←)|)V|u
 3652  r|)2|gq|gα_↓|g1|)|4|"o|41|4α+↓|43|ur(nα+↓1)/2|)|)!(|πmodulo|
 3652  4|εn).|;{A6}|πHere 2|4|"o|4(2|ur(|εqα+↓1)/2|)|))|g2, 
 3655  |πso 2|ur|ε(nα_↓1)/2|)|)|4←"o|4(2|ur(qα+↓1)/2|)|))|g(|gn|gα_
 3656  ↓|g1|g)|4|"o|41 |πby Fermat's theorem. Finally, 
 3661  by a simple case of the law of quadratic reciprocity 
 3671  (exercise 1.2.4<47), |ε3|ur(nα_↓1)/2←)*4)|4←""N4←→α_↓1, 
 3674  |πsince |ε↔ |πmod 3|4α=↓|41 and |εn |πmod 4←4α=↓|43. 
 3682  This means |εV|ur|)2|gq|gα_↓|g1|)|4|"o|4|→α_↓2, 
 3685  |πso |εV|ur|)2|gq|gα_↓|g2|)|4|"oM45[['{A24∧|π|∨E|∨X|∨E|∨R|∨C
 3686  |∨I|∨S|∨E|∨S|'{A12}{H9L11}|9|1|πN≡1|≡.|9|4|ε[|*/|↔O|↔c|\]|9|π
 3687  If the sequence |εd|β0, d|β1, d|β2,|4.|4.|4. 
 3693  |πof trial divisors in Algorithm A contains a 
 3701  number which is not prime, why will it never 
 3710  appearcicnthe ouwput?|'{A3}|9|1|≡2|≡.|9|4|ε[|*/|↔O|↔C|\]|9|πI
 3712  f it is known that the input |εN |πto Algorithm 
 3722  A is equal to 3 or more, could step A2 be eliminated?|'
 3734  {A3}|9|1|≡3|≡.|9|4|ε[M|*/|↔P|↔c|\]|9|πShow that 
 3736  there is a number |εP |πwith the following property: 
 3745  If 1000|4|¬E|4n|4|¬E|41000000, then |εn |πis 
 3750  prime if and only if gcd(|εn,|4P)|4α=↓|41.|'{A3}|9|1|π|≡4|≡.
 3756  |9|4|ε[M|*/|↔P|↔M|\]|9|π(J. M. Pollard.) Prove 
 3760  that (10) is the average value of the least |εn|4|¬R|41 
 3770  |πwith |εy|βn|4α*24y|β2|βn, |πif |εf |πis random 
 3776  modulo |εp.|'{A3}|9|1|≡5|≡.|9|4|ε[|*/|↔P|↔≡|\]|9←π*/se 
 3779  Fermat'↔smethod ton_nd thesfactorksof 10541 by 
 3784  hand.|'{A3}|9|1|≡6←≡.]9*34←ε[[|*/*3↔|↔MN\*4]9*3π4f 
 3786  |ε≥ |π/ssaf oddfprime and if |εN |π/ssnot a multiple 
 3795  of |εp,λ|π#covdsthaw thesnk¬xbjcmxfv¬wquss|≥*5→44¬DS4X44¬}Y4∀
 3797  #,|[)ukv thqw |ε)Fg2]4≠↓**4]N4←""N4;Yv3/|[()mbkwgn|≥≥*2↔|[.qus
 3799  uusbgqwponn|≥≥↔λ|π#ussquaw hon|ε(*41∀I4←¬FN45*2/2#],↓J↓Fπ'|:*35
 3800  4≡6***2[::44≥[*/*/↔P↔**C\]::[αkukkusshhyspvgb∧wxxsmxfpvgggj¬mvcvv
 3800  hhyssuu¬¬smxfUWgggclhmmFfmmnuux¬ckj¬ycvmvqqzjcqqyfnhhystw∧∧w
 3800  ssfmgcussfxgcmmbkqqs |ε*2Miii|π-bmnoo exjctlys=εl 
 3803  an inoegral number of memory words.|'{A3}|9|1|≡8|≡.|9|4|ε[|*/
 3809  |↔P|↔L|\]|9(The ``sieve offEratoszhefes↔''λ|π3⊃dfcdfourys{K9
 3811  X|B)6.]|) Thesfollowing procedure evidefoly dkskovkjksuwlimb
 3815  dfpvcvxsnk¬xbjkspwssshhqknuuvvv¬fnicmz∧∧jc|\], 
 3816  [(uccksiphcjxmv¬ssuwlphhysnmmvvcvxsnk¬xbjk;:sywjghqqphhuwlph
 3816  hysmbdfnk¬xbjkspwssshhqkn \*2(; [πhyfnsukckssuv¬wqysygckksm¬q
 3818  hhhysmvulppples |εp|=|rkNg2, p|βk(p|βk|4α+↓|42), 
 3821  p|βk(p|βk|4α+↓|44),|4.|4.|4. |πof the |εk|πth 
 3825  prime |εp|βk, |πfor |εk|4α=↓|42, 3, 4,|4.|4.|4.|4, 
 3831  |πuntil reaching a primds|εp|βk |πwith |εp|=|βkSg2|4|¬}|4N. 
 3837  |π*3yow ho∧sto ajjql thespcgcjdkjdsjksz ddskrcbddficoonan 
 3842  alggrithmnqqicm issdkrectlyssuitedfhone∃cient 
 3844  computer calculation,,usungnnonmultiplication.←'{A3}|9|1|≡9*3
 3845  ≡.|9←4←ε[[|*/*3↔5|↔**C\**]9*3π1ez |ε↔ |π~bsuknmbdfnk¬xbj,|\*2N44}¬
 3847  C477.|[(Ym∧qhhqwhikfhhysnk¬xbjc|≥\*2≤()) [πxfHHybgjxm7#7##7#↓
 3848  Xiusuufkvvuxgcmxf Q*2n|9|1|≡9|≡.|9|4|ε[M|*/|↔P|↔C|\]|9|πLet 
 3850  |εn |πbe an odd number, |εn|4|¬R|43. |πShow that 
 3858  if the number |ε|≤l(n) |πof Theorem 3.2.1.2B 
 3865  is a divisor of |εn|4α_↓|41 |πbut not equal to 
 3874  |εn|4α_↓|41, |πthen |εn |πmust have the form 
 3881  |εp|β1p|β2|4.|4.|4.|4p|βt |πwhere the |εp'|πs 
 3885  are distinct primes and |εt|4|¬R|43.|'{A3}|≡1|≡0|≡.|9|4|ε[M|
 3890  */|↔P|↔o|\]|9(|πJohn Selfridge.) Prove that if, 
 3895  for each prime divisor |εp |πof |εn|4α_↓|41, 
 3902  |πthere is a number |εx|βp |πsuch that |εx|ur(nα_↓1)/p|)p|) 
 3910  |πmod |εn|4|=|↔6α=↓|41 |πbut |εx|urnα_↓1|)p|) 
 3914  |πmod |εn|4α=↓|41, |πthen |εn |πis prime.|'{A3}|≡1|≡1|≡.|9|4
 3920  |ε[M|*/|↔P|↔c|\]|9|πWhat outputs does Algorithm 
 3924  E give when |εN|4α=↓|4197209, |εk|4α=↓|45, m|4α=↓|41? 
 3930  [Hint|*/:|\ |¬H|v45|4|¬O|4197209|)|4α=↓|4992|4α+↓|4|"C|v41,|4
 3931  495,|42,|4495,|41,|41984|)|"C.]|'{A3}|π|≡1|≡2|≡.|9|4|ε[M|*/|↔
 3932  P|↔l|\]|9|πDesign an algorithm which uses the 
 3938  outputs of Algorithm E to _nd a proper factorization 
 3947  of |εN, |πif a solution to (17) can be found 
 3957  by combininvvhhe outputs of Algorithm E.|'{A3}|≡1|≡3|≡.|9|4|
 3963  ε[M|*/|↔P|↔p|\]|9|πGiven a prime |εp |πand a positive 
 3970  integer |εd, |πwhat is the value of |εf(p,|4d), 
 3978  |πthe average number of times |εp |πdivides |εA|g2|4α_↓|4dB|
 3985  g2, |πwhen |εA |πand |εB |πare random integers 
 3993  that are independent except for the condition 
 4000  gcd(A,|4B)|4α=↓|41?|'{A3}|≡1|≡4|≡.|9|4|ε[M|*/|↔P|↔c|\]|9|πPro
 4001  ve that the number |εT |πin step E3 of Algorithm 
 4011  E will never be a multiple of an odd prime |εp 
 4022  |πfor which |ε(kN)|ur_↓1)/2|)|) |πmod |εp|4|¬Q|41.|'
 4027  {A3}|π|≡1|≡5|≡.|9|4|ε[M|*/|↔L|↔M|\]|9(|πLucas 
 4028  and Lehmer.) Let |εP, Q |πbe relatively prime 
 4036  integers, and let |εU|β0|4α=↓|40, U|β1|4α=↓|41, 
 4041  U|βn|βα+↓|β1|4α=↓|4PU|βn|4α_↓|4QU|βn|βα_↓|β1 
 4042  |πfor |εn|4|¬R|41. |πProve that if |εN |πis a 
 4050  positive integer relatively prime to |ε2P|g2|4α_↓|48Q, 
 4056  |π_nd iff|εU|βNNβα~↓]β1 |π.od |εN|4α=↓|40, |πwhile 
 4061  |εU|ur|)(Nα+↓1)/p|) |πmod |εN|4|=|↔6α=↓|40 |πfor 
 4065  each prime |εp |πdividing |εN|4α+↓|41, |πthen 
 4071  |εN |πis prime. (Thpu gives a test for primality 
 4080  when the factors of |εN|4α+↓|41 |πare known instead 
 4088  of the factors of |εN|4α_↓|41. |πThe value of 
 4096  |εU|βm |πcan be evaluated in |εO(Nπgog|4|εm) 
 4102  |π↔zeps; cf. exercise 4.6.3<26.) [|εHint|*/:|\ 
 4107  |πSee the proof of Theorem L.]|'{A3d|≡↓←≡6|≡.]9*34←ε[M|*/|↔C|↔
 4113  c|\]|9*3π%je there in≠≡clewqsmkkxsMfjksfnfspvcvfs?*3,↓{↓x|≡14≡
 4115  N≡.←9*344ε(MN*/←↔5|↔**C\*4,|π(7.,C.,Prjwt.)↔Ascomvlwzesprooxfoff
 4115  pgcv¬wppyyxxshhyscvmv¬jkssoffFfjvjw"↔sHhebrjmntakkssthssfxgv
 4115  nmxfuuhgjesqqmxssnobdsshq¬xshhysfxgvm|≥*2*2]4=*2),|[≤hejjs|≥≥ 
 4116  |π≠kff|≥_u|π≠jjspgsutpvdsinme∧ejs sawiufyucvchhssfbglg∧unvnu
 4117  jclhmdzpcccvnfkpionf:?(i)↔Ikf|ε(*2Sβ1,]4_|β1)↔]4.]4.N4.←4,,(q
 4117  |βt,|4qSβt) |π_jesthe sons off|ε(q,|4a) |πthen 
 4122  |εq|4α=↓|4q|β1|4.|4.|4.|4q|βk|4α+↓|41. [|πIn 
 4124  particular if (|εq,|4a) |πhas no sons then |εq|4α=↓|42.] 
 4132  |π(ii) If |ε(r,|4b) |πis a son of |ε(q,|4a) |πthen 
 4141  |εa|ur(qα_↓1)/r|)|) |πmod |εq|4|=|↔6α=↓|41. |π(iii) 
 4145  For each node |ε(q,|4a), a|gq|gα_↓|g1 |πmod |εq|4α=↓|41. 
 4152  |πIt follows thaw |≥≥s|π/uspvcmesukff|ε_u|π/usuupvcmcppv¬sco
 4155  oo modkwom|ε≥≡,|π↔brnawlinoddss|≥(q,]4_*2),[]π*4or 
 4157  example↔λthe tree proves that 1009 is prime.] 
 4164  Prove that such astree wuth rooo |ε(q,]4=*2↔|π.assuwhmofyh|≥*2
 4170  (*2*2)|[[mbds↔,qqyjjs|≥*2f|[7usuucjwhyjcsqgowqyvggowcnvnfknctcm
 4170  n.N'{A6}(1009,|411*2*4;*3'(2,|41)!(2,←41)!(2,|41)!(2,|41*2$(7,|4
 4170  444444444444444444444444444444444444444444444444444444444444
 4170  44444444*?(2,|41)!(2,|41)!(2,|41)!(2,|41)!(7,|43)!(3,|42)!(3,
 4170  |42)|;|;{A33}{A6}|≡1|≡8|≡.|9|4|ε[HM|*/|↔P|↔O|\]|9|πGive 
 4173  a heuristic proof of (7), analogous to the text's 
 4182  derivation of (6). What is the approximate probability 
 4190  that |εp|βt|βα_↓|β1|4|¬E|4|¬H|v4p|βt|)|1?|'{A3}|π|≡1|≡9|≡.|9
 4192  |4|ε[M|*/|↔P|↔C|\]|9|π(J. M. Pollard.) Show how 
 4197  to compute a number |εM |πwith the property that 
 4206  |ε|πgcd(|εM,|4N) |πis divisible by those primes 
 4212  |εp |πsuch that |εp|4α_↓|41 |πis a divisor of 
 4220  some given number |εD. [Hint|*/:|\ |πConsider 
 4226  numbers of the form |εa|gn|4α_↓|41.] |πExtend 
 4232  this to an e∃cient method which has high probability 
 4241  of discovering prime factors |εp |πof a given 
 4249  large number |εN, |πwhen all the prime power 
 4257  factors of |εp|4α_↓|41 |πare less than 10|g3 
 4264  except for at most one prime factor less than 
 4273  10|g5. [For example, the second-largest prime 
 4279  dividing (14) should be detected, since it is 
 4287  1|4α+↓|42|g4|4|¬O|45|g2|4|¬O|467|4|¬O|4107|4|¬O|4199|4|¬O|44
 4287  1231.]|'{A3}|≡2|≡0|≡.|9|4|ε[M|*/|↔M|↔c|\]|9|πConsider 
 4289  exercise 19 with |εp|4α+↓|41 |πreplacing |εp|4α_↓|41.|'
 4295  |Ha{U0}{H10L12M29}|πW58320#Computer Programming!ch. 
folio 515 galley 14
 4297  4!f. 515!g. 14|'*1|∨4|∨.|∨6|∨.|9|∨P|∨O|∨L|∨Y|∨N|∨O|∨M|∨I|∨A|∨
 4300  L|4|4|∨A|∨R|∨I|∨T|∨H|∨M|∨E|∨T|∨I|∨C|'|'A |εpolynomial 
 4304  over S |πis an expression of the form|'{A6}|εu(x)|4α=↓|4u|βn
 4312  x|gn|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4u|β1x|4α+↓|4u|β0,|J!(1)|;
 4313  {A6}|πwhere the ``coe∃cients'' |εu|βn,|4.|4.|4.|4,|4u|β1, 
 4317  u|β0 |πare elements of some algebraic system 
 4324  |εS, |πand the ``variable'' |εx |πmay be regarded 
 4332  as a formal symbol with an indeterminate meaning. 
 4340  We will assume that the algebraic system |εS 
 4348  |πis a |εcommutative ring with identity|*/;|\ 
 4354  |πthis means that |εS |πadmits the operations 
 4361  of addition, subtraction, and multiplication, 
 4366  satisfying the customary properties: Addition 
 4371  and multiplication are associative and commutative 
 4377  binary operations de_ned on |εS, |πwhere multiplication 
 4384  distributes over addition; and subtraction is 
 4390  the inverse of addition. There is an additive 
 4398  identity element 0 such that |εa|4α+↓|40|4α=↓|4a, 
 4404  |πandfa multiplicative identity element 1 such 
 4410  that |εa|4|¬O|41|4α=↓|4a, |πfor all |εa |πin 
 4416  |εS. |πThe polynomial |ε0x|gn|gα+↓|gm|4α+↓|4|¬O|4|¬O|4|¬O|4α
 4419  +↓|40x|gn|gα+↓|g1|4α+↓|4u|βnx|gn|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4u
 4419  |β1x|4α+↓|4u|β0 |πis regarded as the same polynomial 
 4426  as (1), altho¬¬vhits expression is formally di=erent.|'
 4433  !|9|4|1|1|1We say that (1) is a polynomial of 
 4441  |εdegree n |πand |εleading coe∀cient u|βn |πif 
 4448  |εu|βn|4|=|↔6α=↓|40; |πand in this case we write|'
 4455  {A6}deg|ε(u)|4α=↓|4n,]!|λ9(u)|4α=↓|4u|βn.|J!(2)|;
 4456  {A6}|πBy convention, we also set|'{A6}|ε|πdeg(0)|4α=↓|4|→α_↓
 4461  |¬X,!!|λ9(0)|4α=↓|40,|J!(3)|;{A6}|πwhere ``0'' 
 4464  denotes the zero polynomial whose coe∃cients 
 4470  are all zero. We say |εu(x) |πis a |εmonic polynomial 
 4480  |πif |ε|λ9(u)|4α=↓|41.|'!|9|4|1|1|1|πArithmetic 
 4483  on polynomials consists primarily of addition, 
 4489  subtrjcoion, and muwtiplication; in some cases, 
 4495  further opejationsssukh ausfkvcsign,nexvonefoiazion,nfjkoorc
 4497  ng, and takkng thesgreazest commonnfkvisor ujrsimportaft. 
 4503  The processes of addition, subtraction, and multiplication 
 4510  are de_ned in a natural way, as though the variable 
 4520  |εx |πwere an element of |εS: |πAddition and 
 4528  subtraction are done by adding or subtracting 
 4535  the coe∃cients of like powers of |εx. |πMultiplication 
 4543  is done by the rule|'{A6}|ε(u|βrx|gr|4α+↓|4|¬O|4|¬O|4|¬O|4α+
 4548  ↓|4u|β0)(#|βsx|gs|4α+↓←4|¬O|4←¬O|4|¬O|4α+↓|4v|β0)|4α=↓|4(w|β
 4548  r|βα+↓|βsx|gr|gα+↓|gs|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4w|β0),|;
 4549  {A3}|πwhere|'|εw|βk|4α=↓|4u|β0v|βk|4α+↓|4u|β1v|βk|βα_↓|β1|4α
 4550  +↓|4|¬O|4|¬O|4|¬O|4α+↓|4u|βk|βα_↓|β1v|β1|4α+↓|4u|βkv|β0.|J!(
 4550  4)|;{A6}|πIn the latter formula |εu|βi |πor |εv|βj 
 4558  |πare treated as zeromicf Q=|4|¬QU4r |πor |εj|4|¬Q|4s.|'
 4565  |π!|9|4|1|1|1The algebraic system |εS |πis usually 
 4571  the set of integers, or the rational numbers; 
 4579  or it may itself be a set of polynomials (in 
 4589  variables other than |εx); |πin the latter situation 
 4597  (1) is a |εmultivariate |πpolynomial, a polynomial 
 4604  in several variables. Another important case 
 4610  occurs when the algebraic system |εS |πconsists 
 4617  of the integers 0, 1,|4.|4.|4.|4, m|4α_↓|41, 
 4623  |πwith addition, subtraction, and multiplication 
 4628  performed mod|4|εm (|πcf. Eq. 4.3.2<11);?this 
 4633  is called |εpolynomiaw arithmetic modulo m.λ|π0he 
 4639  sqekiaw cjsesoffpogyfomcawiujcthmdzicnmodklo 
 4641  2,nwhen eakv offthescoe∃≡ceftssiis*?*?*?*?|πconsists 
 4644  of the integers 0, 1,|4.|4.|4.|4, m|4α_↓|41, 
 4650  |πwith addition, subtraction, and multiplication 
 4655  performed mod|4|εm (|πcf. Eq. 4.3.2<11); this 
 4661  is called |εpolynomial arithmetic modulo m. |πThe 
 4668  special case of polynomial arithmetic modulo 
 4674  2, when each of the coe∃cients is 0 or 1, is 
 4685  especially important.|'!|9|4|1|1|1The reader 
 4689  should note the similarity between polynomial 
 4695  arithmetic and multiple-precision arithmetic 
 4699  (Section 4.3.1), where the radix |εb |πis substituted 
 4707  for |εx. |πThe chief di=erence is that the coe∃cient 
 4716  |εu|βk |πof |εx|gk |πin polynomial arithmetic 
 4722  bears little or no essential relation to its 
 4730  neighboring coe∃cients |εu|βk|β|¬N|β1, |πso the 
 4735  idea of ``carrying'' from one place to the next 
 4744  is absent. In fact, polynomial arithmetic modulo 
 4751  |εb |πis essentially identical to multiple-precision 
 4757  arithmetic with radix |εb, |πexcept that all 
 4764  carries are suppressed. For example, compare 
 4770  the multiplication of (1101)|β2 by (1011)|β2 
 4776  in the binary number system with the analogous 
 4784  multiplication of |εx|g3|4α+↓|4x|g2|4α+↓|41 |πby 
 4788  |εx|g3|4α+↓|4x|4α+↓|41 |πmodulo 2:|'{A6}|∂!!!!!!!!!|∂!!!!!!!
 4791  !!!!!|∂|ES;|>Binary system|;Polynomials modulo 
 4796  2|;>{A2}|>1101!!|9|?1101!!!!|?>|>α⊗↓|1|11011!!|9|?
 4804  α⊗↓|1|11011!!!!|?>{A2}|>1101!!|9|?1101!!!!|?>
 4810  |>1101|9|1!!|9|?1101|9|1!!!!|?>|>1101!|9|1|1|1!!|9|?
 4816  1101!|9|1|1|1!!!!|?>{A2}|>10001111!!|9|?1111111!!!!|?
 4821  >{A6}The product of these polynomials modulo 
 4828  2 is obtained by suppressing all carries, and 
 4836  it is |εx|g6|4α+↓|4x|g5|4α+↓|4x|g4|4α+↓|4x|g3|4α+↓|4x|g2|4α+
 4838  ↓|4x|4α+↓|41. |πIf we had multiplied the same 
 4845  polynomials over the integers, without taking 
 4851  residues modulo 2, the result would have been 
 4859  |εx|g6|4α+↓|4x|g5|4α+↓|4x|g4|4α+↓|43x|g3|4α+↓|4x|g2|4α+↓|4x|
 4859  4α+↓|41; |πagain carries are suppressed, but 
 4865  in this case the coe∃cients can get arbitrarily 
 4873  large.|'!|9|4|1|1|1In view of this strong analogy 
 4880  with multiple-precision arithmetic, it is unnecessary 
 4886  to discuss polynomial addition, subtraction, 
 4891  and multiplication much further in this section. 
 4898  However, we should point out some factors which 
 4906  often make polynomial arithmetic somewhat di=erent 
 4912  from multiple-precision arithmetic in practice: 
 4917  There is often a tendency to have a large number 
 4927  of zero coe∃cients, and polynomials of varying 
 4934  degrees, so special forms of representation are 
 4941  desirable; this situation is considered in Section 
 4948  2.2.4. Furthermore, arithmetic on polynomials 
 4953  in several variables leads to routines which 
 4960  are best understood in a recursive framework; 
 4967  this situation is discussed in Chapter 8.|'!|9|4|1|1|1Althou
 4974  gh the techniques of polynomial addition, subtraction, 
 4981  and multiplication are comparatively straightforward, 
 4986  there are sevdrjlhmohyr impgggwnt asqacts oxnpolynomial 
 4992  arithmetic which ddssrve sqpdcial *?!|9|4|1|1|1Although 
 4997  the techniques of polynomial addition, subtraction, 
 5003  and multiplication are comparatively straightforward, 
 5008  there are several other important aspects of 
 5015  polynomial arithmetic which deserve special examination. 
 5021  The following subsections therefore discuss |εdivision 
 5027  |πof polynomials, with associated techniques 
 5032  such as _nding greatest common divisors; |εfactoring 
 5039  |πof polynomials; and also e∃cient |εevaluation 
 5045  |πof polynomials, i.e., _nding the value of |εu(x) 
 5053  |πwhen |εx |πis a given element of |εS, |πusing 
 5062  as few operations as possible. The special case 
 5070  of evalqating |εx|gn |πvery rapidly when |εn 
 5077  |πis large is quite important, so it is discussed 
 5086  in detail in Section 4.6.3.|'!|9|4|1|1|1The _rst 
 5093  major set of computer subroutines for doing polynomial 
 5101  arithmetic was the ALPAK system [W. S. Brown, 
 5109  J. P. Hyde, and B. A. Tague, |εBell System Technical 
 5119  Journal |π|≡4|≡2 (1963), 2081<2119; |π|≡4|≡3 
 5124  (1964), 785<804, 1547<1562]. Another earl*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 5128